关注
作者:李济民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; }
查看原帖
点赞 评论
相关推荐
牛客热帖
更多
正在热议
更多
# 第一份工作应该选高薪还是热爱? #
66816次浏览 593人参与
# 不考虑薪资和职业,你最想做什么工作呢? #
92085次浏览 679人参与
# 秋招签约后的心态变化 #
82539次浏览 814人参与
# 听劝,这个公司值得去吗 #
486158次浏览 1700人参与
# 你觉得早上几点上班合适? #
72388次浏览 303人参与
# 学历贬值真的很严重吗? #
24484次浏览 174人参与
# 机械人与华为的爱恨情仇 #
120166次浏览 957人参与
# 一人推荐一个值得去的通信/硬件公司 #
186495次浏览 1859人参与
# 打工人的工作餐日常 #
53248次浏览 415人参与
# 哪些公司真双非友好? #
15834次浏览 82人参与
# 26届的你们有几段实习? #
44097次浏览 488人参与
# 月薪多少能在一线城市生存 #
28132次浏览 305人参与
# 双非能在秋招上岸吗? #
221730次浏览 1172人参与
# 你以为的实习VS真实的实习 #
29827次浏览 273人参与
# 今年秋招哪家公司给的薪资最良心? #
252948次浏览 1418人参与
# 你后悔自己读研吗? #
20629次浏览 240人参与
# 当下环境,你会继续卷互联网,还是看其他行业机会 #
117933次浏览 812人参与
# 追觅科技求职进展汇总 #
18265次浏览 120人参与
# 实习想申请秋招offer,能不能argue薪资 #
149942次浏览 932人参与
# 如何KTV领导 #
62793次浏览 472人参与