[NOIP2013 提高组] 积木大赛
题目描述
春春幼儿园举办了一年一度的“积木大赛”。今年比赛的内容是搭建一座宽度为 \(n\) 的大厦，大厦可以看成由 \(n\) 块宽度为 \(1\) 的积木组成，第 \(i\) 块积木的最终高度需要是 \(h_i\)。
在搭建开始之前，没有任何积木（可以看成 \(n\) 块高度为 \(0\) 的积木）。接下来每次操作，小朋友们可以选择一段连续区间 \([l, r]\)，然后将第 \(L\) 块到第 \(R\) 块之间（含第 \(L\) 块和第 \(R\) 块）所有积木的高度分别增加 \(1\)。
小 M 是个聪明的小朋友，她很快想出了建造大厦的最佳策略，使得建造所需的操作次数最少。但她不是一个勤于动手的孩子，所以想请你帮忙实现这个策略，并求出最少的操作次数。
输入格式
包含两行，第一行包含一个整数 \(n\)，表示大厦的宽度。
第二行包含 \(n\) 个整数，第 \(i\) 个整数为 \(h_i\)。
输出格式
建造所需的最少操作数。
样例 #1
样例输入 #1
5
2 3 4 1 2
样例输出 #1
5
提示
【样例解释】
其中一种可行的最佳方案，依次选择：\([1,5]\)，$ [1,3]\(，\)[2,3]\(，\)[3,3]\(，\) [5,5]$。
【数据范围】
- 对于 \(30\%\) 的数据，有 \(1 \leq n \leq 10\)；
- 对于 \(70\%\) 的数据，有 \(1 \leq n \leq 1000\)；
- 对于 \(100\%\) 的数据，有 \(1 \leq n \leq 100000\)，\(0 \leq h_i \leq 10000\)。
思路
- 法一：模拟题意
从前往后依次比较相邻数值大小，如果前面的比后面的大，那么前面的某次操作可以覆盖后面，对答案无贡献；如果前面的比后面小，那么后面的需要额外的操作补足这个高出的部分，高出的部分即为操作的次数
void solve(){
int n, a, ans = 0, last = 0;
cin >> n;
for(int i = 0; i < n; ++ i){
cin >> a;
if(a > last) ans += a - last;
last = a;
}
cout << ans << '\n';
return ;
}
- 法二：维护一个递增的单调栈，那么遇到大数先进栈，遇到小数则前面的操作无法为后面产生继续的贡献，出栈并统计答案。记得最后栈内还有元素时最后一个元素一步操作即可
ll n, a[maxm];
void solve(){
cin >> n;
stack<int> q;
ll ans = 0;
for(int i = 0; i < n; ++ i){
cin >> a[i];
int pre = -1;
while(q.size() && q.top() > a[i]){
if(pre != -1)
ans += pre - q.top();
pre = q.top();
q.pop();
}
if(pre != -1) ans += pre - a[i];
if(q.empty() || q.top() < a[i]){
q.push(a[i]);
}
}
int pre = -1;
while(q.size()){
if(pre != -1)
ans += pre - q.top();
pre = q.top();
q.pop();
}
if(pre != 0 && pre != -1) ans += pre;
cout << ans << '\n';
return ;
}