算法知识点: 差分,贪心
复杂度： )
解题思路：
我们逆向思考：假设给定了每块积木的高度，每次可以将某一段区间中的所有高度减一，问最少操作多少次可以将所有高度变成0。
原序列是： , 其中
。
构造差分序列：
...
则将 中的每个数减1的操作，等价于将
减1, 将
加1。
因此问题变成每次从 中挑两个数，前一个减1，后一个加1，问最少操作多少次可以将所有数变成0。
对于每个正数 ，最少需要操作
次，因此总操作次数等于差分数组中所有正数之和
。
C++ 代码：
#include <iostream>
#include <algorithm>
using namespace std; const int N = 100010;
int n;
int h[N];
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &h[i]);
int res = 0;
for (int i = n; i; i--) res += max(0, h[i] - h[i - 1]);
cout << res << endl;
return 0;
} 
京公网安备 11010502036488号