脚本宝典收集整理的这篇文章主要介绍了【补题】Seg 贪心+均摊+性质+妙妙题，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

题意

给定序列 (A) , 定义 (f(A)) 为序列 (A) 的最大非空子段和。 你可以花费 (1) 的代价，令 (A) 中某个元素 (a_i) 减一。 (g(i)) 的值为花费了 (i) 的代价后最小的 (f(A'))。 求(sum _{i=1} ^K g(i)) 其中 (1 leq n leq 2 times 10^{5},-10^{8} leq a_{i} leq 10^{8}, 1 leq K leq 10^{13})

做法

考虑如何求出单个 (g(k)) 。 考虑二分答案。 设 (S) 为 (A) 的前缀和数组，目前枚举的答案为 (w) 。接下来就是如何判定。 花费代价可以转化成 (S) 后缀减一，则现在就是判定是否存在一种方案使得 (forall i<j,a_j-a_ileq w)。

考虑从前往后贪心。设 (lim) 为后面的数不能超过的阈值。 若 (lim leq a_i)，则进行 (a_i-lim) 次操作，然后令 (lim=min(lim,a_i+w))。 其实不必显式计算出 (lim) 的值，直接令 (lim=a_i) 即可。（因为花费代价的操作为后缀减) 上述贪心不难证明。

我们发现，随着 (k) 的增大，原函数 (g) 的减小将越来越难。且使 (g(i)) 减少 (1) 的代价最多不超过 (n) 一个极端的情况是，若全部的 (a_i) 均为同一负数，则减小 (1) 的代价即为 (O(n)) 的。 因此二分出代价区间即可。 时间复杂度 (O(n^2logw))

这还是太慢了...考虑去除冗余计算，我们的 (lim) 重复计算太多次了。

考虑如何一次计算对于 (w) 的代价。操作仅有两种 (A(w):=A(w)+max left(0, a_{i}-L(w)right), L(w):=max left(a_{i}, L(w)right); \ L(w):=min left(L(w), w+a_{i}right)) 然后大力维护即可

脚本宝典总结

以上是脚本宝典为你收集整理的【补题】Seg 贪心+均摊+性质+妙妙题全部内容，希望文章能够帮你解决【补题】Seg 贪心+均摊+性质+妙妙题所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。