洛谷 P3503 [POI 2010] KLO-Blocks 题解
Solution双指针做法。
本文中合法子段指一段高度 \(\ge k\) 的连续堆。
观察数据范围，发现 \(O(nm)\) 可过。于是考虑对于每个 \(k\) 都 \(O(n)\) 做一遍。
看到最长子段问题，尝试双指针。设以 \(l\) 为左端点的最长合法子段右端点为 \(r\)。易证 \(l\) 递增时 \(r\) 单调不降。
于是只需要 \(O(1)\) 判断一个区间 \(\) 是否合法。显然贪心地把左右两边所有木块尽量往这个区间上集中。设 \(pre_i\) 为第 \(1\sim i\) 堆最多能向 \(i+1\) 贡献多少个木块，\(suf_i\) 同理。\(pre,suf\) 均可以 \(O(n)\) 递推处理。
此时 \(\) 合法等价于 \(pre_{l-1}+suf_{r+1}+\sum_{i=l}^r a_i\le k\cdot (r-l+1)\)。可以 \(O(1)\) 判断。
时间复杂度 \(O(nm)\)。
Code
#include #define rept(i,a,b) for(int i(a);i=b;--i)#define int long longusing namespace std;const int N=1e6+5;int a,s,pre,suf,n,m,k,ans;bool check(int l,int r){ return pre+suf+s-s>=k*(r-l+1);}signed main(){ cin.tie(0)->sync_with_stdio(0); cin>>n>>m; rept(i,1,n) cin>>a,s=s+a; while(m--){ ans=0; cin>>k; rept(i,1,n) pre=max(0ll,a+pre-k); pert(i,n,1) suf=max(0ll,a+suf-k); for(int l=1,r=0;l 分享、互助 让互联网精神温暖你我 懂技术并乐意极积无私分享的人越来越少。珍惜 收藏一下 不知道什么时候能用到 谢谢分享，辛苦了 谢谢分享，试用一下 懂技术并乐意极积无私分享的人越来越少。珍惜 感谢分享，下载保存了，貌似很强大 感谢发布原创作品，程序园因你更精彩 感谢发布原创作品，程序园因你更精彩 收藏一下 不知道什么时候能用到 谢谢分享，辛苦了 前排留名，哈哈哈 感谢，下载保存了 这个好，看起来很实用 东西不错很实用谢谢分享 感谢分享，下载保存了，貌似很强大
页:
[1]