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

C++