题目: https://www.luogu.org/problemnew/show/P3957
先二分一个 g, 然后判断;
由于转移的范围是一个区间, 也就是滑动窗口, 所以单调队列优化;
可以先令队尾为 -1, 但不真的放进去, 为的是第一次判断能否从 0 走到;
普及组的题也要 Narh 提点...
代码如下:
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- using namespace std;
- typedef long long ll;
- int const xn=5e5+5;
- int n,d,k,x[xn],s[xn],q[xn],h,t;
- ll f[xn],inf=1e17;
- int rd()
- {
- int ret=0,f=1; char ch=getchar();
- while(ch<'0'||ch>'9'){if(ch=='-')f=0; ch=getchar();}
- while(ch>='0'&&ch<='9')ret=(ret<<3)+(ret<<1)+ch-'0',ch=getchar();
- return f?ret:-ret;
- }
- void add(int x)
- {
- while(h<=t&&f[q[t]]<=f[x])t--;
- q[++t]=x;
- }
- bool ck(int g)
- {
- h=1,t=0; int mn=max(d-g,1);
- memset(f,-2,sizeof f);
- x[0]=0; q[0]=-1; f[0]=0;
- for(int i=1;i<=n;i++)
- {
- while(x[i]-x[q[t]+1]>=mn)add(q[t]+1);//
- while(h<=t&&x[i]-x[q[h]]>d+g)h++;
- if(h<=t)f[i]=f[q[h]]+s[i];
- if(f[i]>=k)return 1;
- }
- return 0;
- }
- int main()
- {
- n=rd(); d=rd(); k=rd();
- for(int i=1;i<=n;i++)x[i]=rd(),s[i]=rd();
- int l=0,r=max(x[n]-d,d-1),ans=-1;
- while(l<=r)
- {
- int mid=((l+r)>>1);
- if(ck(mid))ans=mid,r=mid-1;
- else l=mid+1;
- }
- printf("%d\n",ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2823881.html