【题解】跳房子

已加缩进，无注释，欢迎参考！！！

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll x[500010],s[500010],dp[500010];
ll n,d,k;
bool work(ll g){
     memset(dp,0,sizeof(dp));
     ll maxx=d+g,QAQ=1;
     ll mini=max(QAQ,d-g);
     deque<int> q;
     int j=0;
     for(int i=1;i<=n;i++){
             for(;x[i]>=x[j]+mini;++j){
                     while(!q.empty()&&dp[j]>dp[q.back()])q.pop_back();
                     q.push_back(j);
             }
             while(!q.empty()&&x[q.front()]+maxx<x[i])q.pop_front();
             if(q.empty())dp[i]=-999999999999;
             else dp[i]=s[i]+dp[q.front()];
             if (dp[i]>=k)return 1;
     }
     return 0;
}
int main(){
    cin>>n>>d>>k;
    ll tmp=0;
    memset(x,0,sizeof(x));
    memset(s,0,sizeof(s));
    for(int i=1;i<=n;i++){
            scanf("%lld%lld",&x[i],&s[i]);
            if (s[i]>0)tmp+=s[i];
    }
    if (tmp<k){cout<<-1;return 0;};
    ll l=0,r=1005,mans=x[n];
    while(l<=r){
                ll mid=(r+l)/2;
                if (work(mid)){mans=mid;r=mid-1;}
                else l=mid+1;
    }
    cout<<mans;
    return 0;
}

以上就是解题思路，谢谢观看！（关注一下吧，必回关……）
洛谷团队：lpk团（加一下吧！）