【第22题】标签有毒[NOIP2018 提高组] 铺设道路

小码匠

发布于 2023-08-31 14:15:13

1760

发布于 2023-08-31 14:15:13

文章被收录于专栏：小码匠和老码农

碎碎念

官方给的标签贪心、树状数组，我看题解，有些大佬用的线段树、树状数组（其实是自己功力还不够）。杀鸡蔫用牛刀，对于蒟蒻的我，更熟悉纯模拟+贪心策略+差分。

题目：[NOIP2018 提高组] 铺设道路

题目原文请移步下面的链接

https://www.luogu.com.cn/problem/P5019
- 参考题解：https://www.luogu.com.cn/problem/P5019
标签：贪心、树状数组
难度：普及-

题解

思路

题解大家可移步看这里，很多童鞋写了各种解法
- https://www.luogu.com.cn/problem/P5019
- 推荐：我醉了学长的：https://www.luogu.com.cn/problem/solution/P5019，递推过程写的很详细。

代码

#include <bits/stdc++.h>
using namespace std;
#define endl '\n';

void best_coder() {
    int n;
    scanf("%d", &n);
    int ans = 0;
    vector<int> a(n);
    int t = 0;
    for (int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
        if (a[i] > t) {
            ans += a[i] - t;
        }
        t = a[i];
    }
    printf("%d", ans);
}

void happy_coder() {

}

int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    // 返回
    return 0;
}

END

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2023-05-24，如有侵权请联系 cloudcommunity@tencent.com 删除

https