洛谷 P3503 [POI 2010] KLO-Blocks 题解

Solution

双指针做法。
本文中合法子段指一段高度 \(\ge k\) 的连续堆。
观察数据范围，发现 \(O(nm)\) 可过。于是考虑对于每个 \(k\) 都 \(O(n)\) 做一遍。
看到最长子段问题，尝试双指针。设以 \(l\) 为左端点的最长合法子段右端点为 \(r\)。易证 \(l\) 递增时 \(r\) 单调不降。
于是只需要 \(O(1)\) 判断一个区间 \([l,r]\) 是否合法。显然贪心地把左右两边所有木块尽量往这个区间上集中。设 \(pre_i\) 为第 \(1\sim i\) 堆最多能向 \(i+1\) 贡献多少个木块，\(suf_i\) 同理。\(pre,suf\) 均可以 \(O(n)\) 递推处理。
此时 \([l,r]\) 合法等价于 \(pre_{l-1}+suf_{r+1}+\sum_{i=l}^r a_i\le k\cdot (r-l+1)\)。可以 \(O(1)\) 判断。
时间复杂度 \(O(nm)\)。
Code

[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[N],s[N],pre[N],suf[N],n,m,k,ans;bool check(int l,int r){    return pre[l-1]+suf[r+1]+s[r]-s[l-1]>=k*(r-l+1);}signed main(){    cin.tie(0)->sync_with_stdio(0);    cin>>n>>m;    rept(i,1,n) cin>>a,s=s[i-1]+a;    while(m--){        ans=0;        cin>>k;        rept(i,1,n) pre=max(0ll,a+pre[i-1]-k);        pert(i,n,1) suf=max(0ll,a+suf[i+1]-k);        for(int l=1,r=0;l

分享、互助 让互联网精神温暖你我