打卡信奥刷题（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”。

他到达的机场就在地铁线的第一站旁边。这条地铁线有 $n$ 个站点，“The World’s Start” 位于最后一个站点。New-Lodnon 的地铁非常快，所以你可以假设从一个站到下一个站只需要一分钟。

Jerry 需要一张地铁通行卡才能使用地铁。每张通行卡都有一个范围 $r$ 和一个价格 $p$。使用范围为 $r$ 的通行卡，Jerry 一次最多可以旅行 $r$ 个站。因此，如果 Jerry 在第 $i$ 个站进入地铁，他应该在从 $i-r$ 到 $i+r$ 的某个站点下车。需要 $d_i$ 分钟才能在第 $i$ 个站点下车并重新进入地铁。在第一站进入或最后一站下车不需要时间。

Jerry 不是很富有，但他有一些空闲时间，所以他决定购买最便宜的通行卡，使他能够在不超过 $t$ 分钟的时间内从第一站旅行到最后一站。

输入格式

输入文件的第一行包含两个整数 $n$ 和 $t$ —— 站点的数量和最大可能的时间 $(2\le n\le 50000$ ; $n-1\le t\le 10^9)$。

第二行包含 $n-1$ 个整数 $p_r$ —— 范围为 $r=1$ 到 $n-1$ 的通行卡的价格 $(1\le p_r\le 100000)$。

第三行包含 $n-2$ 个整数 $d_i$ —— 在第 $i=2$ 到 $n-1$ 站点重新进入地铁所需的分钟数 $(1\le d_i\le 10^5)$。

输出格式

输出一个整数 $p$ —— 允许 Jerry 在不超过 $t$ 分钟内从第一站到最后一站的最便宜的通行卡的价格。

输入输出样例 #1

输入 #1

4 4
1 2 3
1 4

输出 #1

2

说明/提示

时间限制：2 秒，内存限制：256 MB。

题面翻译由 ChatGPT-4o 提供。

C++实现

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 5e4 + 10;
LL n, a[N], w[N], t, ans = 1e18, f[N];
deque<LL>q;
bool check(LL x){
    q.clear();
    q.push_back(1);
    for(LL i = 2; i <= n; 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);
    }
    return f[n] <= t;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> t;
    t -= n - 1;
    for(LL i = 1; i < n; i ++){
        cin >> a[i];
    }
    for(LL i = 2; i < n; i ++){
        cin >> w[i];
    }
    LL l = 1, r = n - 1, mid;
    while(l < r){
        mid = l + r >> 1;
        if(check(mid))r = mid;
        else l = mid + 1;
    }//二分第一个满足条件的
    for(LL i = l; i < n; i ++){
        ans = min(ans, a[i]);
    }//后面都满足条件
    cout << ans;
    return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容

原文地址：https://blog.csdn.net/rogeliu/article/details/159939492

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！