跳房子

作者：李济民233 链接：https://www.nowcoder.com/discuss/123368?type=0&order=0&pos=6&page=0 来源：牛客网 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=500010; const ll INF=(ll)(1e9)*maxn; int n,d,dis[maxn]; ll k,val[maxn]; ll dp[maxn]; deque<int> q; int zuo,you; bool in_range(int j,int i) {     return zuo<=dis[i]-dis[j]&&dis[i]-dis[j]<=you; } bool test(int g) {     if(g>=d)     {         zuo=1;         you=d+g;     }     else     {         zuo=d-g;         you=d+g;     }     for(int i=1;i<=n;i++)     dp[i]=-INF;     int L=0;     q=deque<int>();     for(int i=1;i<=n;i++)     {         if(zuo<=dis[i]&&dis[i]<=you)         dp[i]=val[i];         while(1)         {             if(L+1>=i)             break;             if(dis[i]-dis[L+1]<zuo)             break;             L++;             if(dp[L]==-INF)             continue;             while(!q.empty()&&dp[q.back()]<=dp[L])             q.pop_back();             q.push_back(L);         }         while(!q.empty()&&!in_range(q.front(),i))         q.pop_front();         if(!q.empty())         dp[i]=max(dp[i],dp[q.front()]+val[i]);         if(dp[i]>=k)         return 1;     }     return 0; } int main() {     scanf("%d %d %lld",&n,&d,&k);     int mx=0;     for(int i=1;i<=n;i++)     {         scanf("%d %lld",&dis[i],&val[i]);         mx=max(mx,dis[i]);     }     int l=0,r=mx,ans=-1;     while(l<=r)     {         int mid=(l+r)/2;         if(test(mid))         {             r=mid-1;             ans=mid;         }         else l=mid+1;     }     printf("%d\n",ans);     return 0; }