Codeforces Round #724 Omkar and Medians 题解 (Java/C++)

题解

首先我们可以注意到,对于b[i+1],相比b[i]来说,其实只增加两个数:a[2i+1]和a[2i]。那么这两个数的中位数的影响其实只有一位。
比如[1,3,5,7,9],其中位数是5,现在增加两个数,最多最多使中位数左移1位或者右移1位。

于是我们发现如果b[i+1]==b[i],那么左右随便加一个数即可。

考虑b[i+1]>b[i],那么我们其实是想右移且只能右移1位。因此我们只需要看b[i]右边一位的值x是多少。
如果b[i+1]>x,那没治。不论如何努力,下一步的中位数最多是x。因此无解。
如果b[i+1]==x。那当然非常开心,我们可以随便增加两个较大的数即可。
如果b[i+1]<x,有b[i]<b[i+1]<x,可知b[i+1]一定没有出现过,因此我们新添加的两个数为b[i+1]和任意一个比b[i+1]大的数。

到这里我们就能发现,对于除了添加当前的b[i+1]之外。添加的其他数是什么根本不影响。对于有解的两种情况,本质是b[i+1]是否已经添加过的区别,对于b[i+1]以外的数其实无所谓。因此这个数可以是任意非常大的数。

反过来b[i+1]<b[i]同理。于是就搞定了。

代码

Java

Submission #118736149 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #118739052 - Codeforces
Codeforces. Programming competitions and contests, programming community