AC code (样例#1输出1)

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 500100;
deque<int> q;
int n,k,cnt=0,ans=LLONG_MAX,x[N],dis[N],dp[N],d,sc[N];
map<int,int>ind;
int a[N];
bool check(int money){
	memset(dp,128,sizeof(dp));
	int last=0;
	q.clear();
	int l =max(1ll,d-money) , r=min(dis[n],d+money);
	if(0+l>dis[n]) return 0;
//	printf("When you spend %d,you can get steplen from %d to %d\n",money,l,r);
//	for(int i=0;i<=n;i++){
//		dp[i]=LLONG_MIN+1000000ll+1ll;
//	}
//	q.push_back(0);
	dp[0]=1;
	for(int i=1;i<=n;i++){//q中存下标 
//		if(x[q.front()]>x[i]-l) continue;
		while(dis[last]<=dis[i]-l&&last<i){
			while(!q.empty()&&dp[q.back()]<=dp[last]){
//				printf("%d(dis:%d) is out because of %d(dis:%d)\n",q.back(),dis[q.back()],last,dis[last]);
				q.pop_back();	
			}
//			printf("%d(dis:%d) has been pushed\n",last,dis[last]);
			q.push_back(last);
			last++;
		}
		while(!q.empty()&&(x[q.front()]<x[i]-r)){
//			printf("%d(dis:%d) is out of date\n",q.front(),dis[q.front()]);
			q.pop_front();
		}
		if(!q.empty())dp[i]=dp[q.front()]+sc[i];
//		printf("After jumping from %d,%d' max score is %d\n",q.front(),i,dp[i]);
		if(dp[i]>=k) return 1;
	}
	return 0;
}
signed main(){
//	freopen("P3957_3.in","r",stdin);
	cin>>n>>d>>k;
	int l=0,r=1e9;
	for(int i=1;i<=n;i++){
		cin>>x[i]>>sc[i];
		dis[i]=x[i];
		ind[x[i]]=i;
	}
	while(l<=r){
		int mid=(l+r)>>1;
		if(check(mid)){
//			printf("%d well done!\n",mid);
			ans=min(ans,mid);
			r=mid-1;
		}
		else{
			l=mid+1;
		}
	}
	if(ans==LLONG_MAX){
		cout<<-1;
		return 0;
	}
	cout<<ans;
	return 0;
}

60pts code(WA on3,4,9,10)

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 500100;
deque<int> q;
int n,k,cnt=0,ans=LLONG_MAX,x[N],dis[N],dp[N],d,sc[N];
map<int,int>ind;
int a[N];
bool check(int money){
	int last=1;
	q.clear();
	int l = d-money , r=d+money;
	if(d-money<0){
		l=0;
	}
//	printf("When you spend %d,you can get steplen from %d to %d\n",money,l,r);
	for(int i=0;i<=n;i++){
		dp[i]=LLONG_MIN+1000000ll+1ll;
	}
	q.push_back(0);
	dp[0]=0;
	for(int i=1;i<=n;i++){//q中存下标 
		if(x[q.front()]>x[i]-l) continue;
		while(!q.empty()&&(x[q.front()]<x[i]-r)){
//			printf("%d(dis:%d) is out of date\n",q.front(),dis[q.front()]);
			q.pop_front();
		}
		while(dis[last]<=dis[i]-l&&dis[last]>=dis[i]-r&&last<i){
			while(!q.empty()&&dp[q.back()]<=dp[last]){
//				printf("%d(dis:%d) is out because of %d(dis:%d)\n",q.back(),dis[q.back()],last,dis[last]);
				q.pop_back();	
			}
//			printf("%d(dis:%d) has been pushed\n",last,dis[last]);
			q.push_back(last);
			last++;
		}if(q.empty()) return 0;
		dp[i]=dp[q.front()]+sc[i];
//		printf("After jumping from %d,%d' max score is %d\n",q.front(),i,dp[i]);
		if(dp[i]>=k) return 1;
	}
	return 0;
}
signed main(){
//	freopen("P3957_2.in","r",stdin);
	cin>>n>>d>>k;
	int l=0,r=1e9;
	for(int i=1;i<=n;i++){
		cin>>x[i]>>sc[i];
		dis[i]=x[i];
		ind[x[i]]=i;
	}
	while(l<=r){
		int mid=(l+r)>>1;
		if(check(mid)){
//			printf("%d well done!\n",mid);
			ans=min(ans,mid);
			r=mid-1;
		}
		else{
			l=mid+1;
		}
	}
	if(ans==LLONG_MAX){
		cout<<-1;
		return 0;
	}
	cout<<ans;
	return 0;
}
(以上代码中dis数组与x数组表意相同)

其实更改只有

for(int i=0;i<=n;i++){
    dp[i]=LLONG_MIN+1000000ll+1ll；
}

->

memset(dp,128,sizeof(dp));

r=d+money;

->

r=min(dis[n],d+money);

last=1;
q.push_back(0);
dp[0]=0;

->

last=0;
dp[0]=1;

哪个大犇能帮我解惑？