[NOIP2018 提高组] 铺设道路

_H17_ · 2024-12-24 21:39:32 · 题解

题目分析

我们需要次数最少，又想到了贪心。贪心的说，我们肯定是对一段整体推掉 1 直到有的变成 0。之后又可以分成更小的段继续操作。

怎么分段？我们想起了差分。每次比前一个数增大就是开始了新的一段（显然它前一个数的段会先填好，只剩下它和后面的一些数又成一段）。段的结尾不需要考虑（其实就是减少的时候），因为题目没有让我们说方案，而且结束和开始数量一样。

代码实现

#include<bits/stdc++.h>
using namespace std;
int n;
short a[100001];
int ans;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",a+i);
    ans=a[1];
    for(int i=2;i<=n;i++)
        if(a[i]>a[i-1])
            ans+=a[i]-a[i-1];
        printf("%d",ans);
    return 0;
}