2023 公路 · 方案二单调栈预处理

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

一次算出每个站右边第一个更便宜的站

2023
贪心

正文

// CSP-J 2023 复赛 T2 · 公路（方案二 · 满分）
// 原题：https://oj.yecheng.tv/p/CSPJ2023B
//
// 方案二 · 单调栈预处理「右边第一个更便宜的站」
// 方案一的贪心思路完全正确，慢只慢在每次都要现场找下一个便宜站。
// 这个信息其实可以一次算好：从右往左扫，维护一个油价严格递增的栈，
// 扫到 i 时先把栈顶那些「油价 >= a[i]」的都弹掉，剩下的栈顶就是右边第一个比 i 便宜的站。
//   为什么要弹 >= 的：留下来的必须严格更便宜，相等也不算（相等时在哪买都一样，直接跳过去更省事）。
// 预处理 O(n)，之后每站 O(1) 决策，总复杂度 O(n)。
// 另外注意：买油要按「升」向上取整，写成 (need - oil + d - 1) / d。

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

const int MAXN = 100005;
long long v[MAXN], a[MAXN];
long long dist[MAXN];
int nxtCheaper[MAXN];

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];

    vector<int> st;                            // 单调栈：油价严格递增
    for (int i = n; i >= 1; i--) {
        while (!st.empty() && a[st.back()] >= a[i]) st.pop_back();
        nxtCheaper[i] = st.empty() ? n : st.back();
        st.push_back(i);
    }

    long long oil = 0;
    long long cost = 0;
    for (int i = 1; i < n; i++) {
        int target = nxtCheaper[i];
        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 公路 · 方案二单调栈预处理