CF1244E Minimizing Difference 题解
闲话
吐槽一下，ABC330F 比此题严格更强，但是它评了绿，这题评了蓝。（个人感觉大概都是绿。）
题解
给你一个序列 \(a_i\)，一次操作将一个数的值增加 \(\pm1\)，进行至多 \(k\) 次操作后，求最小 \(\max\{a_i\} - \min\{a_i\}\)。
把序列抽象成一个数轴，其上 \(n\) 个点，第 \(i\) 个点的坐标是 \(a_i\)，一次操作将一个点左移或右移 \(1\) 单位，至多 \(k\) 次操作后，用一条线段盖住所有点，求线段最小长度。
结论
- 为了使线段的位置最优（操作次数少），它必然有一端在一个点上。
证明
能感性理解的话可跳过
注意：以下“包含”、“盖住”指严格包含（在端点上不算包含）。
比如：
将黑色线段左移，其端点刚好碰到一个点时，停下，记为红线。右移，同样碰到点就停下，记为蓝线。（也就是说，它快要盖住或离开一个点时，停止移动。）
这个结论就是，黑色线段 不优于红线 或 不优于蓝线。
因为像我们这样移动黑线，并不会改变任何点的被包含状态（线段不会新覆盖任何点，也不会离开任何点）。
左移线段 \(x\) 单位（\(x\) 可为负，即右移），会使右边没被盖住的点代价增加 \(x\)，左边没被盖住的点代价减少 \(x\)。
那么，如果左边点多，向左移（红线）；右边点多，向右移（蓝线）。这样，红蓝线里必然有一个不劣于黑色。证毕。
这样，没有端点在点上的线段（黑线），都不优于端点在点上的线段（红/蓝线）。那么这些黑线就不用考虑了。
做法
容易想到，短的线段可以覆盖，长的必然也可以。问题单调，考虑二分线段长。
如何 check(x)？
由上面的结论，线段一定有一端在点上。那就可以 \(O(n)\) 枚举线段位置，每个点两种情况：线段的左/右端点在它这里。
考虑快速统计一个位置的代价。前缀和维护坐标和即可 \(O(\log n)\)。
复杂度 \(O(n \log n \cdot \log V)\)，\(V\) 是坐标值域。
题外话：ABC330F 题解
这个东西转成二维了，但是其实它的 \(x\) 和 \(y\) 是分开的，因为是曼哈顿距离。所以 \(x\) 和 \(y\) 分别排序，共用 \(k\) 的贡献即可。
复杂度还是 \(O(n \log n\cdot\log V)\)，\(V\) 为坐标值域。
标签：右移,log,蓝线,左移,CF1244E,端点,线段 From： https://www.cnblogs.com/C01et10n/p/17957965