今天咱家心情好，去2013年的题看了看，不幸的遇到了一道水题
题目简述：给你一个长度为n的目标序列，你每次可以把某一个区间中所有的值加一，问最少需要多少次操作才可以把一个长度为n的0序列变成目标序列
来看看这家伙，区间修改！我直接无脑打了个线段树模板，然而发现卵用没有，虽然网上有一些题解是贪心+线段树的，然而我们不需要线段树也可以直接贪到100分，而且要比线段树快，因为我们是O n 做的
咱家不会贪心证明，咱家只能在这跟你们瞎咧咧几句咱家的理解：每次只能+1 ，这是一个很好的性质，然后我们来想想一下可能的数据类型 ①很平很平，像2 3 3 3 3这种飞机都可以起飞了，②喜马拉雅山，像是1 2 1 3 8844 1 2 3 这种，好像有难度 ③ 天山山脉 1 233 23 2333 14 567 这样随时可以有一个极高点 ④渐高渐低型1 10 20 30 40 30 20 10 1 这种类型，我们需要想一种策略能应对多样的数据，接下来就要开始说说贪心的可行性了：我们可以把当前的高度与前面一个的高度比较，倘若比前面的高，那我们就需要在前面的高度上在向上盖，倘若比前面的低，那么前面的在盖的时候一定可以把当前位置达到目标，所以我们只需要累加所有h[i] - h[i] > 0 的值即为答案。我们在回到那个1 的问题，正是因为每次加一才能这样贪心，如果每次的高度自定的话，显然是不可行的，一旦有空的高度就一定会错误
#include <algorithm> #include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <cmath> using namespace std; typedef long long ll; int main(){ int n,x1 = 0,x2 = 0; ll ans = 0; scanf("%d",&n); for (int i = 0;i < n; ++i){ scanf("%d",&x1); if (x1 > x2) ans += x1 - x2; x2 = x1; } printf("%lld\n",ans); return 0; }
原文：http://www.cnblogs.com/GENEVE/p/4805641.html