首先我们可以发现，若 (a_l) ~ (a_r) 的平均值大于等于 (k) ，则这个区间一定可以转化为都大于等于 (k) 的。我们就把这个问题化简成了”求最长的平均值大于等于 (k) 的子序列”。
再去化简，可以发现，如果我们把序列中的每一项都减去 (k) ，再求前缀和 (s) ，若 (s_i-s_j\ge 0) ，则区间 ((j,i)) 一定满足条件。
那么我们考虑如何求这种区间。
不难发现， 若(i
那么我们去维护一个单调栈存可能最优的左端点，栈中的元素都满足：在栈中 (j) 在 (i) 之上且 (s_i>s_j) 。（这里自己好好思考一下）
根据我们维护的单调栈的性质，我们可以发现：
那么我们再从最右边开始枚举右端点，去找最大区间。如果一个右端点与栈顶的左端点可以构成合法区间那就更新答案，并把栈顶弹出（因为再靠左的右端点就算满足条件也没有这个长了），继续看浮出来的新栈顶是否合法。
记得判断 (s_i\ge 0) 的情况。
#include
#define _for(i,a,b) for(int i=a;i=b;--i)
#define ll long long
using namespace std;
const int N=1e5+10,inf=0x3f3f3f3f;
ll n,q,a[N],b[N],k,ans;
stacks1,s2;
int main(){
scanf("%lld%lld",&n,&q);
_for(i,1,n)scanf("%lld",&a[i]);
while(q--){
scanf("%lld",&k);
ans=0;
_for(i,1,n){
b[i]=b[i-1]+a[i]-k;
if(b[i]>=0)ans=max(ans,(ll)(i));
if(s1.empty()||b[i]=0){
ans=max(ans,i-s1.top()),s1.pop();
}
}
printf("%lld\n",ans);
}
return 0;
}
Original: https://www.cnblogs.com/Keven-He/p/15826462.html
Author: Keven-He
Title: 「题解报告」Blocks
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/587591/
转载文章受原作者版权保护。转载请注明原作者出处！