CF1799F Halve or Subtract 题解
蒟蒻君HJT
·
·
题解
好题但是简单题，放 1+2 的 \text{F} 过分了。
考虑对于每个数有四种状态：除 + 减，除，减，什么都不干。
-
引理 1：操作全用完一定不劣。
-
引理 2：对于除 + 减的数，一定先除后减。
接下来将所有数从大到小排序，得到 a_1,a_2,\cdots a_n。
显然除 + 减的一定是一段前缀 k。直接枚举前缀 k。
为了方便，令 \max(0,k1+k2-n)\leq k\leq \min(k1,k2)。鉴于引理 1，这样做没问题。
剩下了 k1-k 个除和 k2-k 个减。
- 引理 3：除了 a_1,a_2,\cdots a_k 之外，进行操作的数字必然是 a_{k+1},a_{k+2}\cdots a_{k1+k2-k}。
对于 a_{k+1},a_{k+2},\cdots a_{k1+k2-k}，按照与 b 的大小关系，分成两段：a_{k+1},a_{k+2},\cdots a_p 与 a_{p+1},a_{p+2},\cdots a_{k1+k2-k}。
假设已经给两段分配好了各自除和减的数量，怎么确定具体的对每个数字的操作呢？
-
- 对于不小于 b 的 a_{k+1},a_{k+2},\cdots a_p：
减操作的贡献一定是 -b，而除操作对于 a_x 的贡献是 -\lfloor \frac{a_x}{2}\rfloor。
既然减给谁都无所谓，那么显然是给大的数除，给小的数减。
即对于 a_{k+1},a_{k+2},\cdots a_p 的操作是： ///---。
-
- 对于小于 b 的 a_{p+1},a_{p+2},\cdots a_{k1+k2-k}：
对于 a_x，减操作的贡献是 -a_x，除操作的贡献是 -\lfloor \frac{a_x}{2}\rfloor。显然，我们应给大的数减，给小的数除。
即对于 a_{p+1},a_{p+2},\cdots a_{k1+k2-k} 的操作是：---///。
发现了什么？从 a_{k+1} 到 a_{k1+k2-k} 的操作是先除，再减，最后除。
所以我们不用真的对 a_x 根据 b 分段，只需要在枚举 k 之后，再枚举减的一段的开头 a_p 即可。可以通过简单 \mathcal{O}(n) 预处理达到单次 \mathcal{O}(1) 算出一个方案的答案。
时间复杂度 \mathcal{O}(n^2)。
code