AcWing 1090. 绿色通道
原题链接
中等
作者:
wangyj
,
2021-01-22 09:47:12
,
所有人可见
,
阅读 502
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,w[50005],f[50005],q[50005];
bool check(int k){
f[0]=0;
int h=0,t=0,i,ans=1e9;
for(i=1;i<=n;i++){
if(h<=t&&q[h]<i-k-1)h++;
f[i]=f[q[h]]+w[i];
while(h<=t&&f[q[t]]>=f[i])t--;
q[++t]=i;
}
for(i=n-k;i<=n;i++)ans=min(ans,f[i]);
return ans<=m;
}
int main()
{
scanf("%d%d",&n,&m);
int l=0,r=n,i,mid;
for(i=1;i<=n;i++)scanf("%d",&w[i]);
while(l<r){
mid=l+r>>1;
if(check(mid))r=mid;else l=mid+1;
}
printf("%d\n",r);
return 0;
}