题解 洛谷 P5019 [NOIP2018 提高组] 铺设道路

P5019 [NOIP2018 提高组] 铺设道路

本题还有一道姐妹题，两题题意一样，代码也一模一样。

简要题意

给你一个序列，每次选取一个区间对这个区间内所有数都减去 $1$，使得区间内至少一个数变成 $0$，重复执行这一过程直到整个序列都为 $0$，求最小操作次数。

策略分析

本题可以用贪心在 $O(n)$ 复杂度完成。

操作方法

我们可以从头往尾扫，设第 $i$ 个位置的值为 $v_i$，当第 $i$ 个位置的值大于第 $i-1$ 个位置的值时，我们就要给答案加上 $v_{i-1}-v_i$，否则不操作。为了后面能够正常操作，第一次必须将第一个位置的直接减到 $0$。

正确性证明

考虑如果 $v_i \le v_{i-1}$， 那我们在填第 $i-1$ 个坑的时候一定可以把第 $i$ 个坑填上；而当 $v_i> v_{i-1}$ 时，我们填第$i$ 个坑的时候又可以顺便把第 $i-1$ 个坑填上，由此递推即可得出答案。

代码

#include <iostream>
#include <cstdio>
using namespace std;

namespace SHAWN {
    const int N = 1e5 + 7;
    int v[N];
    long long ans;
    int work()
    {
        int n;
        cin >> n;
        for (int i = 1; i <= n; ++i) { cin >> v[i]; }
        ans = v[1];
        for (int i = 2; i <= n; ++i) {
            if (v[i] > v[i - 1]) {
                ans += (v[i] - v[i - 1]);
            }
        }
        cout << ans << '\n';
        return 0;
    }
}

signed int main() {
    ios :: sync_with_stdio(false);
    cin.tie(nullptr);
    return SHAWN :: work();
}