CF2042C 题解

__vector__ · 2024-12-04 01:27:55 · 题解

考虑将一个完整的区间拆成两段的贡献是什么。

假设 [l,r] 拆为 [l,mid],[mid+1,r]。

那么 [mid,n] 所有鱼的价值加 1。

注意到，此时本质上是从 mid+1 开始，每个点的编号加了 1。

也就是说，问题转化为：[2,n] 共 n-1 个点，对于每个点，都可以选择是否将从这个点开始的所有点的价值加 1。

假设一条鱼如果是 Bob 获得，那么是 1，反之 -1，设 p_i 代表前 i 个鱼的前缀和。

假设第 i 个点选择将其开始的所有点价值加 1，那么 Bob 领先 Alice 的分数将会增加 p_n-p_{i-1}。

接下来排序贪心就可以。