AcWing 1090. 绿色通道
原题链接
中等
作者:
ZTEG
,
2019-11-04 20:10:30
,
所有人可见
,
阅读 2087
二分答案+单调队列优化的DP验证答案
#include<bits/stdc++.h>
using namespace std;
int n,t;
int a[50005];int f[50005];
int x[50005];int y[50005];
bool kkk(int m)
{
memset(f,0,sizeof(f));//一定要初始化
int l=0,r=1;//为什么 l=0 r=1 相当于直接初始化了一个特殊0点 区间是[l,r) (包含l,不包含r)
for(int i=1;i<=n;i++)
{
while(r>l&&i-x[l]>m+1) l++;//维护单调队列
f[i]=y[l]+a[i];
while(r>l&&y[r-1]>=f[i]) r--;//维护单调队列
x[r]=i;y[r++]=f[i];//添加
}
int MIN=100000001;
for(int i=n;i>=n-m;i--)
MIN=min(MIN,f[i]);//在最后的几个中找到最小值
return MIN<=t; //最小值与 t 比较,返回
}
int main()
{
int ans=100000001;
cin>>n>>t;
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
int l=0,r=n,mid;
while(l<=r)//二分答案
{
mid=(l+r)/2;
if(kkk(mid))
{
ans=min(ans,mid);
r=mid-1;
}
else
l=mid+1;
}
cout<<ans;
return 0;//再见了您嘞
}
棒!
谢谢!!!