关注
作者:李济民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; }
查看原帖
点赞 评论
相关推荐
求offer的大角牛:你可以去****上投投看看,牛客大多数是it开发,技术支持,测试类的工作
点赞 评论 收藏
分享
05-21 16:15
门头沟学院 算法工程师 
点赞 评论 收藏
分享
牛客热帖
更多
- 1... 🌟择难路,未有疑,四非学院本运气拉满,春招拿下大厂后端6.6W
- 2... 秋招应该侧重准备哪个部分的内容1.2W
- 3... 恋爱四年没想到过自己会出轨7436
- 4... 史上最细SQL实战系列:sql笔试例题总结篇(建议收藏)7293
- 5... 其实主包早就找到工作了,但还是每天都刷6630
- 6... 双非二本的漫漫游戏开发春招路Ver2.0——失业、感悟、再出发(万字长文)4928
- 7... 离开软件测试才发现外面没有雨4551
- 8... 从天坑文科到大二腾讯的经历3718
- 9... 25届毕业现在在家呆了一个多月,没工作3575
- 10... 字节拒绝、百度毁约,7.1 腾讯 Offer 到手:25 届双非碎碎念(25届最晚Offer)3330
正在热议
更多
# 实习生的蛐蛐区 #
10335次浏览 90人参与
# 社会教会你的第一课 #
4985次浏览 89人参与
# 现代汽车前瞻技术研发急速编程挑战赛 #
41037次浏览 292人参与
# 应届生,你找到工作了吗 #
7702次浏览 74人参与
# 神州信息工作体验 #
12884次浏览 63人参与
# 简历当中有水分算不算造假? #
8495次浏览 90人参与
# 说说你知道的学历厂 #
5332次浏览 49人参与
# 你认为小厂实习有用吗? #
2337次浏览 37人参与
# 歌尔求职进展汇总 #
55140次浏览 335人参与
# 被AI治愈的瞬间 #
56567次浏览 618人参与
# 双非应该如何逆袭? #
178699次浏览 3108人参与
# 秋招盘点:机械人值得去的企业 #
73234次浏览 671人参与
# 毕业旅行去哪玩儿 #
9525次浏览 130人参与
# 三一集团提前批进度交流 #
23731次浏览 139人参与
# 没有合适的工作,你会先找个干着,还是考公考研 #
117434次浏览 1134人参与
# 哪一瞬间觉得自己长大了 #
902次浏览 32人参与
# 非技术岗投递进展 #
145864次浏览 1264人参与
# 数字马力求职进展汇总 #
180166次浏览 1489人参与
# 材料进Fab厂真的劝退吗? #
44627次浏览 184人参与
# 春招进度记录 #
345787次浏览 3377人参与
# 下班后的时间你怎么安排 #
859次浏览 20人参与