题解：AT_agc053_b [AGC053B] Taking the middle

suzhikz · 2024-12-20 12:48:47 · 题解

套路的，因为给 Aoki 和 Takahashi 两个人的权值和相同，所以转化为取出中位数的最小值。

第 i 次我们可以取出 [n-i+1,n+i] 中的任意一个值，这样为什么对呢？假设我们做完了 n 次，并给其中 Aoki 取得数打了标记。然后我们只需要去离中间最近的那个值即可。为什么一定对呢？假设我们做完了中间的一个区间，若里面的属于 Aoki 的等于一半，扩展时直接取新扩展的不属于 Aoki 的点即可，若大于一半，则取离中间最近的，这样子中位数一定属于 Aoki。

q.push(a[i]);q.push(a[n*2+1-i]);
ans+=a[i];ans+=a[n*2+1-i];
ans-=q.top();q.pop();