p3534 sol（POI2012 STU）

AllenJYL · 2024-12-19 16:27:55 · 题解

极值问题考虑二分答案。首先，对于答案 w，如果没有 a_k=0 的限制，那么我们只需要满足 |x_i-x_{i-1}|\le w。

考虑对序列执行如下操作：

• 对于 i 从 1 至 n，令 x_i\larr\min(x_i,x_{i-1}+w)；
• 对于 i 从 n 至 1，令 x_i\larr\min(x_i,x_{i+1}+w)。

感性理解即可证明这个序列合法且最优，最优指的是元素尽量小。这部分的贡献可以提前算出。

考虑 k，那么需要令 x_i\larr\min(x_i,w\times|i-k|)，暴力计算这部分的贡献肯定超时。

考虑到 |x_i-x_{i+1}|\le w，那么

• 若 i>k，x_{i+1}>w\times|i+1-k|，那么 x_i>w\times|i-k|；
• 若 i<k，x_i>w\times|i-k|，那么 x_{i+1}>w\times|i+1-k|。

据此，可得 x_i>w\times|i-k| 的一定是一个区间，而且是一个两端点随 k 增大而增大的区间。动态维护即可。