P1969 [NOIP2013 提高组] 积木大赛
题目
春春幼儿园举办了一年一度的“积木大赛”。今年比赛的内容是搭建一座宽度为 \(n\) 的大厦，大厦可以看成由 \(n\) 块宽度为 \(1\) 的积木组成，第 \(i\) 块积木的最终高度需要是 \(h_i\)。
在搭建开始之前，没有任何积木（可以看成 \(n\) 块高度为 \(0\) 的积木）。接下来每次操作，小朋友们可以选择一段连续区间 \([l, r]\)，然后将第 \(L\) 块到第 \(R\) 块之间（含第 \(L\) 块和第 \(R\) 块）所有积木的高度分别增加 \(1\)。
小 M 是个聪明的小朋友，她很快想出了建造大厦的最佳策略，使得建造所需的操作次数最少。但她不是一个勤于动手的孩子，所以想请你帮忙实现这个策略，并求出最少的操作次数。
输入
包含两行，第一行包含一个整数 \(n\)，表示大厦的宽度。
第二行包含 \(n\) 个整数，第 \(i\) 个整数为 \(h_i\)。
输出
建造所需的最少操作数。
样例
输入
5
2 3 4 1 2
输出
5
提示
样例解释
其中一种可行的最佳方案，依次选择：\([1,5]\)，$ [1,3]\(，\)[2,3]\(，\)[3,3]\(，\) [5,5]$。
数据范围
- 对于 \(30\%\) 的数据，有 \(1 \le n \le 10\)；
- 对于 \(70\%\) 的数据，有 \(1 \le n \le 1000\)；
- 对于 \(100\%\) 的数据，有 \(1 \le n \le 100000\)，\(0 \le h_i \le 10000\)。
思路
通过思考分析，可以将对区间整体积木增加高度 \(1\) 的操作改为对最终高度的积木做区间减 \(1\) 的操作，这将意味着所有的操作都是对区间进行减法操作。为了降低区间修改的时间复杂度，将题目中最终积木高度的数组转换成差分数组。例如：将“\(2,3,4,1,2\)”原数组转换为差分数组“\(2,1,1,-3,1\)”。由于原数组通过变换后最终所有数字都相同且都为 \(0\)，此时对应的差分数组也都为 \(0\)。由于对原数组的区间 \(\lbrack L,R ]rbrack\) 的减 \(1\) 操作是对差分数组区间 \(\lbrack L,R + 1 \rbrack\) 操作，使得原数组最终变成 \(0\)。其中有几个细节问题，如：
-
对原数组区间 \(\lbrack 1,p \rbrack\) 进行“\(-k\)”操作，对应差分数组是对 \(1\)，\(p+1\) 位置数字进行“\(-k,+k\)”操作。
-
对原数组区间 \(\lbrack p,n \rbrack\) 进行“\(-k\)”操作，对应差分数组是对 \(p\) 位置数字进行“\(-k\)”操作，由于 \(n+1\) 已经超出数组范围，因此对 \(n+1\) 位置的数是否做计算对最终的结果无影响。
为了使原数组变为 \(0\)，差分数组也变成 \(0\)，求最少操作，可以执行成对的“\(-1,+1\)”操作，
差分数组进行“\(-1,+1\)”操作后，最终变成所有数字均不小于 \(0\)。例如最后的差分数组假设为
| 位置 | 数值 |
|---|---|
| 1 | 2 |
| 2 | 0 |
| 3 | 0 |
| 4 | 1 |
| 5 | 0 |
可以两次对第 \(1\) 个位置的数字进行“\(-1\)”操作，对第 \(6\) 个位置的数字进行“\(+1\)”操作；一次对第 \(4\) 个位置的数字进行“\(-1\)”操作，对第 \(6\) 个位置的数进行“\(+1\)”操作。这样，便能用最少的操作次数使得差分数组中所有的数字变成 \(0\)。
思考，假如“\(-1,+1\)”操作成对进行后，差分数组仍有数值小于 \(0\)，说明需要进一步通过“\(+1,-1\)”操作才能使差分数组所有数值最终为 \(0\)。然而“\(+1,-1\)”成对操作则意味着对原数组执行的是区间加法操作，这与题目分析中的第一点相矛盾。
综合可得，“\(-1,+1\)”成对操作的次数就是差分数组中正数之和。
代码
#include <bits/stdc++.h>
using namespace std;
int n, ans, a[100010], b[100010];
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ )
{
scanf("%d", &a[i]);
b[i] = a[i] - a[i - 1];
}
for (int i = 1; i <= n; i ++ )
{
if (b[i] > 0)
ans += b[i];
}
printf("%d", ans);
return 0;
}