题解：CF847H Load Testing

CF847H 题目传送门

题目大意

给定一个序列，你可以对序列中的任意元素进行若干次操作，每次操作一个一个元素

+1

，你的任务是确定最少进行多少次操作能将序列变成一段严格递增之后又严格递减。整个序列严格递增或严格递减是允许的。

解决思路

明显的前缀和，不用会超时。分别从左到右再从右到左枚举将给定数列分别变成单调递增数列和单调递减数列的次数，并顺便计算前缀和。

CPP

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];

注意事项

1 \leq a_i \leq 10^9

，需要开 long long。

代码展示

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;
}

题解：CF847H Load Testing

文章操作

CF847H 题目传送门

题目大意

解决思路

注意事项

代码展示

相关推荐

评论

题解：CF847H Load Testing