BZOJ3043: IncDec Sequence题解

Description
给定一个长度为n的数列{a1,a2…an}，每次可以选择一个区间[l,r]，使这个区间内的数都加一或者都减一。
问至少需要多少次操作才能使数列中的所有数都一样,并求出在保证最少次数的前提下,最终得到的数列有多少种。

Input
第一行一个正整数n
接下来n行,每行一个整数,第i+1行的整数表示ai。
。

Output
第一行输出最少操作次数
第二行输出最终能得到多少种结果

Sample Input
4

1

1

2

2

Sample Output

1

2

HINT
对于100%的数据，n=100000，0<=ai<2147483648

solution：

因为设b为a的差分数组

由于差分的性质，改一段区间就是修改左右端点的差分数组值。

即：

修改 $[L,R]$[L,R]区间(+1)

那么 $b\left[L\right]++,b[R+1]--;$b[L]++,b[R+1]−−;

最后要达到b数组整个为0的情况

所以我们的差分数组就可以正负抵消。

当然要顾及到不能抵消的数组。

于是正负取个 $max$max就行了

不同的次数就是 $max-min+1$max−min+1(???)

然后合并一下就是 $abs\left(\right)+1;$abs()+1;

#include<cstdio>
#include<iostream>
using namespace std;
int a[100005],b[100005];
int abs(int x)
{
	if(x<0)return -x;
	return x;
}
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	int ans1=0,ans2=0;
	for(int i=2;i<=n;i++)
	{
		b[i]=a[i]-a[i-1];
		if(b[i]>0)ans1+=b[i];
		else ans2-=b[i];
	}
	printf("%d\n%d\n",max(ans1,ans2),abs(ans1-ans2)+1);
	return 0; 
}