CF上一道交互题的思考

题目传送门: http://codeforces.com/contest/897/problem/D

题目大意

有N张白纸等待被填数。有M轮游戏,每次分配给你一个数,你需要填到某一个位置上。必须要填进去某一个,可以是拱掉原来的某一个数。
当写的数成为非递减的队列时,游戏直接结束。提供数字的在[1..c], n*[c/2] <= M <= 1000.

题目已经保证了在适当的策略下,一定是有必胜的策略的,玄机就在于这个M >= n*[c/2],即每一个位置都至少会有一半可选的数

解法:

我们希望填的时候,序列前面的元素尽量小,后面的元素尽量大,这样我们就方便在中间插入。

  • 如果小于等于c / 2的话,从前面贪心地填充。即:一直找到一个空的位置或者a[i]>x的位置把它替换掉,这样就保证了整个序列一直在保持着更优(位置增加或者)
  • 如果它大于它从后面充满贪心。一直找到一个空的位置或者a[i]<x的位置把它替换掉。

给一个我自己关于这个解法正确性的证明,首先这两个序列是不会相交的,因为如果相交,则说明已经产生出解出来了,然后假设最后在pos相交,对于1..pos,其每个格子都小于等于c/2,并且由于每一次填的时候都填的空的或者小的,所以其需要的轮数<=pos*c/2;对于后面的pos+1..n,其所有格子的大小都大于c/2,且其序列和只会更大,因此需要的轮数<=(n-pos)*c/2。综上可以得到,其总轮数<=n*c/2,这正和题意给的条件是一致的,因此该解法正确。

参考代码:

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注