P5019 [NOIP2018 提高组] 铺设道路

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

简要题意

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

策略分析

本题可以用贪心在 复杂度完成。

操作方法

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

正确性证明

考虑如果 ， 那我们在填第 个坑的时候一定可以把第 个坑填上；而当 时，我们填第 个坑的时候又可以顺便把第 个坑填上，由此递推即可得出答案。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#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();
}