BZOJ-3043: IncDec Sequence

[文章目录]

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;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注