2023 公路 · 方案一朴素贪心

CSP-J 标程 · 复赛真题 · 代码 · cpp · 难度 2/5 · 共 1459 字

每次现场找下一个更便宜的站

2023
贪心

正文

// CSP-J 2023 复赛 T2 · 公路
// 原题：https://oj.yecheng.tv/p/CSPJ2023B
// 题意：n 个站点排成一排，站点 i 到 i+1 的距离是 v[i]，站点 i 的油价是 a[i]（只卖整数升）。
// 油箱无限大，每升油能跑 d 公里。从站点 1 空油箱出发，问到站点 n 最少花多少钱。
//
// 方案一 · 朴素贪心（直观，n 大时会超时）
// 贪心策略：在站点 i，往后找第一个油价比 i 便宜的站点 t。
//   · 找到了：就在 i 买刚好够开到 t 的油（不够就向上取整）；
//   · 找不到：说明后面都比这里贵，干脆在 i 一次买够开到终点的油。
// 为什么对：油是越往前越便宜就越该提前买，所以「只买到下一个更便宜的站」永远不会吃亏。
// 这一版每次都从头往后扫着找 t，总复杂度 O(n^2)；满分请看法二。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
long long v[MAXN], a[MAXN];
long long dist[MAXN];      // dist[i]：站点 1 到站点 i 的累计距离

int main() {
    freopen("road.in", "r", stdin);
    freopen("road.out", "w", stdout);

    int n;
    long long d;
    cin >> n >> d;
    for (int i = 1; i < n; i++) cin >> v[i];
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i < n; i++) dist[i + 1] = dist[i] + v[i];

    long long oil = 0;     // 油箱里还能再跑多少公里
    long long cost = 0;
    for (int i = 1; i < n; i++) {
        int target = n;
        for (int j = i + 1; j <= n; j++) {     // 找右边第一个更便宜的站
            if (a[j] < a[i]) {
                target = j;
                break;
            }
        }
        long long need = dist[target] - dist[i];
        if (oil < need) {
            long long buy = (need - oil + d - 1) / d;   // 向上取整
            cost += buy * a[i];
            oil += buy * d;
        }
        oil -= v[i];                                     // 开到下一站
    }
    cout << cost << "\n";
    return 0;
}

2023 公路 · 方案一 朴素贪心

正文

CSP-J 标程 · 复赛真题的其它内容

2023 公路 · 方案一朴素贪心