【题解】Luogu 1969【积木大赛】

分析

这里考虑贪心吧,其实很自然的就会想到从左往右枚举,然后对于每个区间,每次都加到满为止,然后直接模拟的话就会TLE,于是得再想想。

因为这样考虑的话对于每个积木,如果它比前一个矮,那么肯定在之前的操作中就把它加满了,于是它对答案的贡献就是0,然后如果它比前一个高,那么继续要做的操作显然就是它的高度减去前一个的高度,累加即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<cstdio>
#include<algorithm>
const int MAXN = 100000 + 6;
int A[MAXN];

int main(){
int n,cnt = 0;scanf("%d",&n);
for(int i = 1;i <= n;i++) scanf("%d",&A[i]);
for(int i = 1;i <= n;i++) if(A[i] > A[i - 1]) cnt += A[i] - A[i - 1];
printf("%d",cnt);

return 0;
}
分享到