题解：CF847H Load Testing
Rex01
·
·
题解
CF847H 题目传送门
题目大意
给定一个序列，你可以对序列中的任意元素进行若干次操作，每次操作一个一个元素 +1，你的任务是确定最少进行多少次操作能将序列变成一段严格递增之后又严格递减。整个序列严格递增或严格递减是允许的。
解决思路
明显的前缀和，不用会超时。分别从左到右再从右到左枚举将给定数列分别变成单调递增数列和单调递减数列的次数，并顺便计算前缀和。
for(int i = 2; i <= n; i++)
//计算单调递增次数与前缀和
{
b[i] = max(b[i - 1] + 1, a[i]);
c[i] = c[i - 1] - a[i] + b[i];
}
for(int i = n - 1; i >= 1; i--)
//计算单调递减次数与前缀和
{
d[i] = max(d[i + 1] + 1, a[i]);
e[i] = e[i + 1] - a[i] + d[i];
}
最终用如下公式计算结果即可：sum = max(b[i], d[i]) + c[i] + e[i + 1] - b[i];
注意事项
## 代码展示
```cpp
#include <bits/stdc++.h>
#define ll long long
//十年OI一场空,不开long long见祖宗
using namespace std;
const int N = 1e5 + 10;
ll n, a[N], b[N], c[N];
//b[],c[],d[],e[]计算将数列变成
//单调递增或递减次数和前缀和
ll d[N], e[N], ans = 2e9, sum;
int main()
{
scanf("%lld", &n);//建议scanf,更快
for(int i = 1; i <= n; i++)
scanf("%lld", &a[i]);
b[1] = a[1];
for(int i = 2; i <= n; i++)
//计算将数列变成单调递增次数与前缀和
{
b[i] = max(b[i - 1] + 1, a[i]);
c[i] = c[i - 1] - a[i] + b[i];
}
d[n] = a[n];
for(int i = n - 1; i >= 1; i--)
//计算将数列变成单调递减次数与前缀和
{
d[i] = max(d[i + 1] + 1, a[i]);
e[i] = e[i + 1] - a[i] + d[i];
}
ans = min(e[1], c[n]);
for(int i = 2; i < n; i++)
{
sum = max(b[i], d[i]) + c[i] + e[i + 1] - b[i];
if(sum < ans) ans = sum;//计算答案并取最小值
}
printf("%lld\n", ans);//建议printf,更快
return 0;
}
```