奇妙的东西
查看原帖
奇妙的东西
520544
Phrvth楼主2022/8/10 21:37

这是我的AC代码

#include<bits/stdc++.h>

using namespace std;
#define INF 1e18
typedef long long ll;
struct node{
	ll pos=0,value=0;
}a[500005];
ll n,d,k;
ll dp[500005];
bool check(ll minn,ll maxx){
	for(int i=1;i<=n;i++) dp[i]=-INF;
	dp[0]=0LL;
	deque<int> q;
	int now=0;
	for(ll i=1;i<=n;i++){
		while(a[i].pos-a[now].pos>maxx&&now<i) now++;
		while(a[i].pos-a[now].pos<=maxx&&a[i].pos-a[now].pos>=minn&&now<i){
			while(!q.empty()&&(dp[q.back()]<=dp[now]||a[i].pos-a[q.back()].pos>maxx)) q.pop_back();	
	//		while(!q.empty()&&a[i].pos-a[q.front()].pos>maxx) q.pop_front();
			q.push_back(now);
			now++;
		}
		while(!q.empty()&&a[i].pos-a[q.front()].pos>maxx) q.pop_front();
		if(!q.empty()) dp[i]=dp[q.front()]+a[i].value;
		if(dp[i]>=k) return true;
	}
	return false;
}
int main()
{
	cin>>n>>d>>k;
	for(ll i=1;i<=n;i++) cin>>a[i].pos>>a[i].value;
	ll l=1,r=a[n].pos;
	while(l<r){
		ll mid=(l+r)>>1;
		if(check(max((long long)1,d-mid),d+mid)) r=mid;
		else l=mid+1; 
	}
	cout<<(r==INF?-1:r);
	return 0;
 } 

大家可以看到我把一行注释掉了,又可以发现在这一行的下面有一行和他一模一样的代码

这就是我的疑惑,把那行代码放到while里面就不行了?(虽然我知道并不需要

哪位大佬可以帮我解决一下这个问题

2022/8/10 21:37
加载中...