传送门
二分答案 主要是判断函数 我们用的是减去mid的前缀和 成立条件是，存在form[i]<form[j]&&j-i>=m
代码如下：
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n,m; long long l,r; long long num[100005],form[100005]; int check(long long ans){ long long M=0; form[0]=0; for(int i=1;i<=n;i++){ form[i]=form[i-1]+num[i]-ans; if(i>=m){ M=min(M,form[i-m]); if(form[i]>M){ return 1; } } } return 0; } long long dmax(long long a,long long b){ return a<b?b:a; } int main(){ scanf("%d%d",&n,&m); num[0]=0; r=0; for(int i=1;i<=n;i++){ int x; scanf("%d",&x); x=x*10000; r=dmax(r,x); num[i]=x; } l=0; long long mid; while(l<=r){ mid=(l+r)/2; if(check(mid)){ l=mid+1; }else{ r=mid-1; } } printf("%lld",l/10); return 0; }