P4552 [Poetize6] IncDec Sequence 差分

题目不难,但是思路巧妙。

我们求出差分数组后,就变成了这三种操作

1.一个数加一
2.一个数减一
3.一个数加一的同时一个数减一

我们要让 (2) ~ (n) 变成 (0) ,设所有整数的和为 (s1) ,负数的和的绝对值为 (s2) ,则最少操作数为 (max(s1, s2))

我们 (min(s1, s2)) 次就让 (s1,s2) 中的一个变成了 (0),剩余的 (max(s1, s2) - min(s1, s2)) 次可以对位置1操作,加上开始的值,一共有 (max(s1, s2) - min(s1, s2) + 1) 种取值。

#include<iostream>
#include<cstdio>
using namespace std;
int n, ans;
long long sum1, sum2;
const int N = 100010;
int a[N];
int main()
{
	cin >> n;
	for (int i = 1; i <= n; ++i)scanf("%d", &a[i]);
	for (int i = n; i >= 1; --i)a[i] -= a[i - 1];
	for (int i = 2; i <= n; ++i)
		(a[i] > 0 ? sum1 : sum2) += a[i];
	sum2 = -sum2;
	cout << max(sum1, sum2) << endl << (max(sum1, sum2) - min(sum1, sum2)) + 1;
}
原文地址:https://www.cnblogs.com/wljss/p/12601546.html