这是我的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里面就不行了?(虽然我知道并不需要)
哪位大佬可以帮我解决一下这个问题