无解解法($O(1)$)

• 直接输出-1

#include<bits/stdc++.h>
using namespace std;
int main()
{
	cout<<-1; 
	return 0;
}

动态规划+二分(80pts)

• 二分当前需要的金币数目
• 令 $f[i]$ 表示走到$i$的最大分数，枚举调过来的位置。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=500010;
int n,d,k;
int dist[N],w[N];
LL f[N];
bool check(int x)
{
	int L=max(1,d-x); //最短跳跃距离
	int R=d+x; //最大跳跃距离
	memset(f,0xcf,sizeof f);
	f[0]=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=i-1;j>=0;j--)
		{
			
			if(dist[j]+R<dist[i]) break; 
			//如果j+最远距离也到不了i号格子，那么j之前的也到不了 
			if(dist[j]+L>dist[i]) continue;
			//j+最小的步数也小于i号格子，继续j之前的格子
			//说明当前格子一定可以跳
			f[i]=max(f[i],f[j]+w[i]);
			if(f[i]>=k) return true; 
		}
	}
	return false;//和没有办法超过k 
}
int main()
{
	cin>>n>>d>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>dist[i]>>w[i];
	} 
	int l=0,r=1e9; //二分范围
	while(l<r)
	{
		int mid=l+r>>1;
		if(check(mid)) r=mid;
		else l=mid+1;
	}
	if(check(l)) cout<<l;
	else cout<<-1;
	return 0;
}

## 动态规划+二分+单调队列(100pts)

• 二分当前需要的金币数目
• 令 $f[i]$ 表示走到$i$的最大分数，枚举调过来的位置。
• 枚举过来的时候其实是区间最大值，可以用单调队列优化。

#include<bits/stdc++.h>
using namespace std;
const int N=500010;
typedef long long LL;
int n,d,k;
int x[N],w[N];
LL f[N];
int q[N];
bool check(int mid)
{
    int l=max(1,d-mid),r=d+mid; //最短距离和最大距离
    LL res=0;
    int hh=0,tt=-1; //单调队列
    memset(f,-0x3f,sizeof f); //初始化距离
    f[0]=0;
    for(int i=1,j=0,k=0;i<=n;i++) //j是窗口第一个位置,k是最后一个位置
    {
        while(x[i]-x[k]>=l) //超过了最短距离，将这些点都入队
        {
            while(hh<=tt&&f[q[tt]]<=f[k]) tt--; //删除以前的队尾的小的元素
            q[++tt]=k++;
        }
        while(x[i]-x[j]>r) j++; //超过了最大距离，需要将当前点出队
        while(hh<=tt&&q[hh]<j) hh++;
         
        //当前剩余在队列之中的点就是可以跳到x[i]的，且队头元素为最大值
        if(hh<=tt) //存在元素
        {
            f[i]=f[q[hh]]+w[i]; //更新可以到x[i]的最大值
        }
        res=max(res,f[i]); //更新全局最大值
    }
    return res>=k;
}
int main()
{
    scanf("%d%d%d",&n,&d,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&x[i],&w[i]);
    }
    int l=0,r=1e9; //枚举左右跳跃距离
    while(l<r)
    {
        int mid=l+r>>1;
        if(check(mid)) r=mid; //说明mid过大，且mid可能是答案
        else l=mid+1; //mid过小，且mid不可能是答案
    }
    if(!check(r)) r=-1;
    printf("%d",r);
    return 0;
}