P5019 题解

ikunTLE · 2024-12-24 22:01:59 · 题解

题目传送门

思路

考虑贪心。想要答案最小，就要使每次填的坑最尽可能多。不难想到可以先把前面的坑填上，填后面的坑时就可以顺带把前面坑填上。如果不能一起填就只能单独填。

形式化来讲，若 d_i\le d_{i-1}，那么可以一起填，后面的答案不变。反之若 d_i>d_{i-1}，那么后面只能单独填，答案增加 d_i-d_{i-1}。

AC CODE

#include<bits/stdc++.h>
using namespace std;
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=1e5+10;
int a[N];
int main(){
    int n=read();
    for(int i=1;i<=n;++i)
        a[i]=read();
    int ans=a[1];
    for(int i=2;i<=n;++i)
        if(a[i]>a[i-1])
            ans+=a[i]-a[i-1];
    printf("%d\n",ans);
    return 0;
}