CF1832D2 - Red-Blue Operations (Hard Version)

yokai_ing · 2025-03-28 22:13:33 · 题解

CF1832D2 Red-Blue Operations (Hard Version)

一道贼恶心的贪心。。

首先，每一个位置的颜色肯定是先红后蓝的，而时间递增，加或减的i也是递增的，所以当红色朝上时一定是<=原数的（因为减每个+后都有一个-），所以操作让一个数变尽量大，一定要让减的那个数和加的那个数尽可能接近。

因此，设操作i次，最后一次时间为t，蓝色朝上（ i \& 1 ）时，贡献v=\lfloor{\frac{i}{2}}\rfloor+t，红色朝上就v=\lfloor{\frac{i}{2}}\rfloor。（都是最大贡献）

发现了贪心策略后，我们仍然不知道该把每个数操作为哪个值最优，自然就想到要去二分答案了。