10.16T1 二分+单调队列优化DP

考场上想了一个小时还是想出来了，题解后来想来还是很简单：

先二分失败值，然后在里面尝试找最长不超过mid的失败值和的最大值

发现只能在mid范围里面找，我们就可以用单调队列来优化，复杂度就是卡不掉的nlogn了

code：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #define N 200006
 5 using namespace std;
 6 long long read(){
 7     long long x=0,f=1;
 8     char c=getchar();
 9     while(!isdigit(c)){
10         if(c=='-')f=-1;
11         c=getchar();
12     }
13     while(isdigit(c)){
14         x=(x<<3)+(x<<1)+c-'0';
15         c=getchar();
16     }
17     return x*f;
18 }
19 long long f[N],n,t,q[N],a[N];
20 bool check(long long mid){
21     memset(f,0,sizeof f);
22     memset(q,0,sizeof q);
23     long long head=0,tail=0;
24     q[head]=0;
25     for(long long i=1;i<=n+1;i++){
26         while(head<=tail&&q[head]<max(i-mid-1,0ll))head++;
27         f[i]=f[q[head]]+a[i];
28         while(head<=tail&&f[q[tail]]>=f[i])tail--;
29         q[++tail]=i;
30     }
31     if(f[n+1]>t)return false;
32     else return true;
33 }
34 int main(){
35 //    freopen("ibn.in","r",stdin);    
36 //    freopen("ibn.out","w",stdout);
37     n=read(),t=read();
38     for(long long i=1;i<=n;i++){
39         a[i]=read();
40     }
41     long long l=0,r=n,ans=0;
42     while(l<=r){
43         long long mid=l+r>>1;
44 //        cout<<"mid->"<<mid<<endl;
45         if(check(mid))ans=mid,r=mid-1;
46         else l=mid+1;
47     }
48     cout<<ans;
49     return 0;
50 }

over