题目：https://codeforces.ml/problemset/problem/1392/C
题意 【算法|【题解】Codeforces Global Round 10 -- C】输入一串数，每次选择一串不降序列，使该序列中所有数全部+1。
求出至少经过多少次操作能使原序列整体变为不降序列。
题解 从右向左遍历原序列，当前遍历到的数为a[i]，前一个数为a[i-1]。若a[i] < a[i-1]，则将a[i]补至a[i-1]即可；若a[i] > a[i-1]，则无视之，不需做任何操作。
算法正确性比较明显：从右向左遍历遍历到数a[i]时，a[i+1],a[i+2],…a[n] 已形成一个不降序列了。此时需要填补的次数为 a[i-1] - a[i] ，即只需考虑a[i-1]与a[i]的差值即可。后面的数不需考虑，因为填补a[i]时可以顺便把后面的数一起填了。
#include
using namespace std;
typedef long long ll;
int t, n, a[200020];
ll ans;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> t;
while (t--){
cin >> n;
ans = 0;
for (int i = 1;
i <= n;
i++)
cin >> a[i];
for (int i = n;
i >= 1;
i--)
if (a[i] < a[i-1])
ans += a[i-1] - a[i];
cout << ans << endl;
}
return 0;
}
推荐阅读
- 人工智能|干货！人体姿态估计与运动预测
- 分析COMP122 The Caesar Cipher
- 技术|为参加2021年蓝桥杯Java软件开发大学B组细心整理常见基础知识、搜索和常用算法解析例题（持续更新...)
- 笔记|C语言数据结构——二叉树的顺序存储和二叉树的遍历
- C语言学习(bit)|16.C语言进阶——深度剖析数据在内存中的存储
- Python机器学习基础与进阶|Python机器学习--集成学习算法--XGBoost算法
- 数据结构与算法|【算法】力扣第 266场周赛
- 数据结构和算法|LeetCode 的正确使用方式
- leetcode|今天开始记录自己的力扣之路
- 人工智能|【机器学习】深度盘点（详细介绍 Python 中的 7 种交叉验证方法！）