[文章目录]
Description
给定一个长度为n的数列{a1,a2...an}，每次可以选择一个区间[l,r]，使这个区间内的数都加一或者都减一。问至少需要多少次操作才能使数列中的所有数都一样,并求出在保证最少次数的前提下,最终得到的数列有多少种。n<=100000
将原数组差分，那么每一个数就是查分数组的前缀和。然后每次修改映射到查分数组上就是[1,n+1]随便两个数，一个+1，另一个-1。最后期望状态就是第一个数不等于0,2~n都为0。
那么答案就是2~n的差分数组里负数与正数绝对值的大的那一方。
最后的数列其实都是差分数组的第一位的值。第一位可能出现的值得个数就是答案。发现差分数组的+1-1过程其实可以在n+1上做文章。所以均到1上的值可能是0~abs之差。正数与负数绝对值之差的绝对值+1就是答案
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,a[101000],b[101000];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",a+i);
b[i]=a[i]-a[i-1];
}
long long suma=0,sumb=0;
for(int i=2;i<=n;i++)
{
if(b[i]>0) suma+=b[i];
else sumb-=b[i];
}
if(suma<sumb) swap(suma,sumb);
printf("%lld\n%lld\n",suma,suma-sumb+1);
return 0;
}