给出一个长度为 n 的序列 a，每次可以进行三种操作中的一种：
- 选择 i，将 1,2,⋯ ,a1,a2,⋯,ai 减 1。
- 选择 i，将 ,+1,⋯ ,ai,ai+1,⋯,an 减 1。
- 将所有 ai 加 1。
求最少需要多少次操作将所有 ai 变为 0。
1≤2×1041≤T≤2×104，1≤≤2×1051≤n≤2×105，−109≤≤109−109≤ai≤109，∑≤2×105∑n≤2×105。
输入 #1
4 3 -2 -2 -2 3 10 4 7 4 4 -4 4 -4 5 1 -2 3 -4 5
输出 #1
2 13 36 33
用一个变量 a 来记录把所有树统一成同一个高度时所需的操作次数。
当我们遇到一棵树高为 ℎh 的树的时候，有以下两种可能的情况：
-
如果 ℎ≤a 那么把前面的树操作 h−a 次使高度统一。
-
否则把在这棵树上操作 a−h 次把它的高度将为 a。
我们发现在两种情况下我们都要操作 ∣h−a∣ 次，最后不要忘记给答案再加上∣a∣ 次操作使得所有树的高度都变为 0。
//https://www.luogu.com.cn/problem/CF1700C #include<bits/stdc++.h> using namespace std; const int N=2e5+10; long long res,n,h,last_tree,now_tree,t; int main() { cin>>t; while(t--) { cin>>n>>last_tree; h=last_tree,res=0; for(int i=1;i<n;i++) { cin>>now_tree;//读入现在树的高度; res+=abs(last_tree-now_tree);//无论前一棵树比它高还是低,要进行的步骤始终是两者之差的绝对值 if(last_tree>=now_tree) h+=(now_tree-last_tree); //如果这棵树比上颗矮,那么由于上棵树是已经更新之后,也就是减去了一定的高度 //这棵树那必定也会减去相同的高度,那么我们需要维护的高度就变成了 上一颗树变成这棵树所需要的次数加上现在的高度 last_tree=now_tree;//更新现在树的高度 } res+=abs(h); cout<<res<<endl; } return 0; }