T4 跳房子 二分答案 单调队列

跳房子，也叫跳飞机，是一种世界性的儿童游戏，也是中国民间传统的体育游戏之一。
　　跳房子的游戏规则如下：
　　在地面上确定一个起点，然后在起点右侧画 n 个格子，这些格子都在同一条直线上。每个格子内有一个数字（ 整数），表示到达这个格子能得到的分数。玩家第一次从起点开始向右跳， 跳到起点右侧的一个格子内。第二次再从当前位置继续向右跳，依此类推。规则规定：玩家每次都必须跳到当前位置右侧的一个格子内。玩家可以在任意时刻结束游戏，获得的分数为曾经到达过的格子中的数字之和。
　　现在小 R 研发了一款弹跳机器人来参加这个游戏。但是这个机器人有一个非常严重的缺陷，它每次向右弹跳的距离只能为固定的 d。小 R 希望改进他的机器人，如果他花 g 个金币改进他的机器人，那么他的机器人灵活性就能增加 g， 但是需要注意的是，每次弹跳的距离至少为 1。 具体而言， 当g < d时， 他的机器人每次可以选择向右弹跳的距离为 d-g, d-g+1,d-g+2， …， d+g-2， d+g-1， d+g； 否则（ 当g ≥ d时），他的机器人每次可以选择向右弹跳的距离为 1， 2， 3， …， d+g-2， d+g-1， d+g。
　　现在小 R 希望获得至少 k 分，请问他至少要花多少金币来改造他的机器人。

#include<cmath>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<map>
const int maxn=500005;
using namespace std;
//int n,d,k;
//int len[maxn],value[maxn],dp[maxn],que[maxn*2];
//（因为单调）二分+动态规划+（用单调队列优化） 
//我觉得单调队列最难理解
//当每次i加1后，会有上面部分j退出区间，也会有尾部的j加入区间，此时如果重新遍历区间求最大值就会浪费---所以维护一个单调队列
//包含区间内的部分j，使得对头的dp最大，队尾的dp最小，每次取队头的位最大值
//单调队列会自动过滤无用的j，保持dp[j]单调 
/*
int maxcost(int a){
	memset(dp,-127,sizeof(dp));
	int head=1,tail=0;
	int mi=max(1,d-a);
	int mx=d+a;
	int rt=0,fir=-1;
	que[++tail]=0,dp[0]=0;
	for(int i=1;i<=n;i++){
		if(len[i]<mi) continue;
		if(len[i]>=mi&&fir==-1) fir=i;
		if(len[i]-len[i-1]>mx) break; //过不去 
		while(len[i]-len[fir]>=mi&&fir<i){
			while(head<=tail&&dp[fir]>dp[que[tail]]) tail--;  //把无用的队尾丢掉 
			if(dp[fir]!=-0x7f7f7f7f) que[++tail]=fir;  //把对头的弄到队尾来？ 
			fir++;
		}
		while(head<=tail&&len[que[head]]+mx<len[i]) head++;  //把无用的队头丢掉 
		if(head>tail) dp[i]=-0x7f7f7f7f;
		else dp[i]=dp[que[head]]+value[i];
		if(dp[i]>rt) rt=dp[i];
	}
	return rt;
}
*/
//上面是单调队列的写法，还可以用deque双端队列
//下面直接用动态规划也可以

long long f[maxn],a[maxn][2],n,d,k,lpos,rpos;
bool check(int g){
	lpos=d-g;rpos=d+g;
	if(lpos<=0) lpos=1;
	memset(f,-127,sizeof(f));//先把dp数组初始化为一个很小的值
	f[0]=0 ; //起点
	for(int i=1;i<=n;i++){
		for(int j=i-1;j>=0;j--){ //用前面的去优化后面的 
			if(a[i][0]-a[j][0]<lpos) continue; //太靠左
			if(a[i][0]-a[j][0]>rpos) break; //太靠右
			f[i]=max(f[j]+a[i][1],f[i]);
			if(f[i]>=k) return 1; 
		}
	} 
	return 0;
}

int main(){
	cin>>n>>d>>k;
	/*
	for(int i=1;i<=n;i++){
		cin>>len[i]>>value[i];
	}
	int left=0,right=len[n];
	while(left!=right){
		int mid=(left+right)>>1;
		if(maxcost(mid)>=k) right=mid;
		else left=mid+1;
	}
	if(maxcost(left)<k) cout<<"-1"<<endl;
	else cout<<left<<endl; 
	*/
	for(int i=1;i<=n;i++){
		cin>>a[i][0]>>a[i][1];
	}
	int ans=-1,l=0,r=20001,m=(l+r)/2;
	while(l<=r){
		if(check(m)){
			ans=m;
			r=m-1;
		}
		else l=m+1;
		m=(l+r)/2;
	}
	cout<<ans<<endl;
return 0;
}