[BZOJ]3043: IncDec Sequence 差分

Description

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

Solution

GDOI后这题就是SB题了。直接差分后乱搞即可。

Code

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define pa pair<int,int>
const int Maxn=100010;
const int inf=2147483647;
int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x*f;
}
int n,a[Maxn],b[Maxn];LL A=0,B=0,C=0,ans;
int main()
{
	n=read();a[0]=0;
	for(int i=1;i<=n;i++)a[i]=read();
	for(int i=1;i<=n;i++)b[i]=a[i]-a[i-1];
	for(int i=2;i<=n;i++)
	{
		if(b[i]<0)A-=b[i];
		if(b[i]>0)B+=b[i];
	}
	ans=min(A,B);C=max(A,B)-min(A,B);
	printf("%lld\n%lld",ans+C,C+1);
}