打卡信奥刷题（3080）用C++实现信奥题 P7057 [NWRRC 2015] Journey to the “The World’s Start”

P7057 [NWRRC 2015] Journey to the “The World’s Start”题目描述Jerry Prince 是一名四年级学生他去 New-Lodnon 参观最受欢迎的游乐园 “The World’s Start”。他到达的机场就在地铁线的第一站旁边。这条地铁线有nnn个站点“The World’s Start” 位于最后一个站点。New-Lodnon 的地铁非常快所以你可以假设从一个站到下一个站只需要一分钟。Jerry 需要一张地铁通行卡才能使用地铁。每张通行卡都有一个范围rrr和一个价格ppp。使用范围为rrr的通行卡Jerry 一次最多可以旅行rrr个站。因此如果 Jerry 在第iii个站进入地铁他应该在从i−ri - ri−r到iri rir的某个站点下车。需要did_{i}di​分钟才能在第iii个站点下车并重新进入地铁。在第一站进入或最后一站下车不需要时间。Jerry 不是很富有但他有一些空闲时间所以他决定购买最便宜的通行卡使他能够在不超过ttt分钟的时间内从第一站旅行到最后一站。输入格式输入文件的第一行包含两个整数nnn和ttt—— 站点的数量和最大可能的时间(2≤n≤50000(2 \le n \le 50 000(2≤n≤50000;n−1≤t≤109)n - 1 \le t \le 10^{9})n−1≤t≤109)。第二行包含n−1n - 1n−1个整数prp_{r}pr​—— 范围为r1r 1r1到n−1n - 1n−1的通行卡的价格(1≤pr≤100000)(1 \le p_{r} \le 100 000)(1≤pr​≤100000)。第三行包含n−2n - 2n−2个整数did_{i}di​—— 在第i2i 2i2到n−1n - 1n−1站点重新进入地铁所需的分钟数(1≤di≤105)(1 \le d_{i} \le 10^{5})(1≤di​≤105)。输出格式输出一个整数ppp—— 允许 Jerry 在不超过ttt分钟内从第一站到最后一站的最便宜的通行卡的价格。输入输出样例 #1输入 #14 4 1 2 3 1 4输出 #12说明/提示时间限制2 秒内存限制256 MB。题面翻译由 ChatGPT-4o 提供。C实现#includebits/stdc.husingnamespacestd;typedeflonglongLL;constintN5e410;LL n,a[N],w[N],t,ans1e18,f[N];dequeLLq;boolcheck(LL x){q.clear();q.push_back(1);for(LL i2;in;i){while(!q.empty()q.front()i-x)q.pop_front();f[i]f[q.front()]w[i];while(!q.empty()f[q.back()]f[i])q.pop_back();q.push_back(i);}returnf[n]t;}intmain(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cinnt;t-n-1;for(LL i1;in;i){cina[i];}for(LL i2;in;i){cinw[i];}LL l1,rn-1,mid;while(lr){midlr1;if(check(mid))rmid;elselmid1;}//二分第一个满足条件的for(LL il;in;i){ansmin(ans,a[i]);}//后面都满足条件coutans;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容