洛谷P5019 铺设道路 题解 模拟/贪心基础题

题目链接：https://www.luogu.org/problemnew/show/P5019
这道题目是一道模拟题，但是它有一点贪心的思想。
我们假设当前最大的深度是 \(d\) ，那么我们需要把所有深度为d的坑全都填成深度为 \(d-1\) ，然后去填深度为 \(d-1\) 的坑……
实现代码如下（手动开启了O2优化，不然会TLE2组）：

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
const int maxn = 100010;
int n, d[maxn], dmax, cnt;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i ++) {
        scanf("%d", d+i);
        dmax = max(dmax, d[i]);
    }
    for (; dmax > 0; dmax --)
        for (int i = 0; i < n; i ++)
            if (d[i] >= dmax && (!i || d[i-1] < dmax)) cnt ++;
    printf("%d\n", cnt);
    return 0;
}

洛谷P5019 铺设道路 题解 模拟/贪心基础题

原文：https://www.cnblogs.com/codedecision/p/11782491.html