P4552 [Poetize6] IncDec Sequence

Link

题目描述

给定一个长度为 \(n\) 的数列 \({a_1,a_2,\cdots,a_n}\)，每次可以选择一个区间 \([l,r]\)，使这个区间内的数都加 \(1\) 或者都减 \(1\)。

请问至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列有多少种。

输入格式

第一行一个正整数 \(n\)

接下来 \(n\) 行,每行一个整数,第 \(i+1\) 行的整数表示 \(a_i\)。

输出格式

第一行输出最少操作次数

第二行输出最终能得到多少种结果

输入输出样例

输入 #1

输出 #1

1

2

说明/提示

对于 100% 的数据，\(1n\le 100000, 0 \le a_i \le 2^{31}\)。

差分的水题。

首先对于第一问的话，我们可以对原序列差分一下，然后我们两种区间操作就变成了，一个值加一，一个值减一。

我们要让操作次数尽可能的小，所以每次要尽量的把一个正数和负数凑在一起进行操作。

设所有差分数组正数的和 \(a\),负数的和为 \(b\),那么我们的最小操作次数就是 \(max(-a,b)\)

对于第二问的话，我们进行了 \(min(-a,b)\) 次操作之后，肯定只会剩下一个负数或者正数 \(x\)，剩下的数就全为零。

我们剩下的几次操作就只能对 \(a_1,x\) 或者 \(x,a_{n+1}\) 进行操作。

然后对 \(a_1\) 进行 \(0,1,2,3,4...x\) 操作所得到的答案也是不同，所以第二问的答案为 \(abs(-a-b)+1\)

Code

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

#define int long long

int n,sum1,sum2,ans;

int a[100010],d[100010];

inline int read()

{

	int s = 0,w = 1; char ch = getchar();

	while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}

	while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0'; ch = getchar();}

	return s * w;

}

signed main()

{

	n = read();

	for(int i = 1; i <= n; i++) a[i] = read();

	for(int i = 1; i <= n; i++)

	{

		d[i] = a[i] - a[i-1];

	}

	for(int i = 2; i <= n; i++)

	{

		if(d[i] < 0) sum1 += d[i];

		if(d[i] > 0) sum2 += d[i];

	}

	ans = max(abs(sum1),sum2);

	printf("%lld\n",ans);

	printf("%lld\n",abs(-sum1-sum2)+1);

	return 0;

}

巴特西