挣扎了一天搞明白的题......嗐。

下面是题目复述。

Description

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

Input

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

Output

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

Sample Input

Sample Output

Hint

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

分析过程：

差分过程可以通过递归求出。
在求完差分之后，第一项的差分是a1先不管它，然后因为正数是指后面的数字比前面的多1，而负数是比前面的数字少1，如果进行调整就以最前面为基准。（因为如果划分区间之后，b2+1，a2后面的所有划定区间的都会+1，也就算是所有的负数都自增1。-1同理。）在正负抵消过之后剩余的数据要自己变为与其他数据相同的值，所以取正数和负数之中的最大值。
在第一问中的抵消过程中最后只会有一种结果，这里不再做过多讨论。（如果还有后续操作（数组正负不对称）这个数字也会被改变，不作为最终答案）
后续操作：当正负抵消不彻底的时候，最后会剩下0和一个正数/负数 n（所有都可以推成极端的一个数字）。然后该数字和前后的调整方法有n+1种（比如说0010可以把前两个数字+1或者后两个数字-1；0020可以把前两个数字-2或者后两个数字+2或者前两个自减1后两个自增1，以此类推......）所以最后的答案是abs（tmp1-tmp2）+1。

PS.一定要注意数组越界和int类型溢出的问题。

PPS.（最开始要排序后来发现着实没用就放弃了-_-）

下面是AC代码。


#include <iostream>
#include<cstdio>
#include<climits>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
int n;
const int N =1e7;
ll a[N],b[N];
ll tmp1=0,tmp2=0;

void insert1(int l,int r,int c)
{
    b[l]+=c;
    b[r+1]-=c;
}
int main()
{
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
    {
        scanf("%lld",&a[i]);
        insert1(i,i,a[i]);
    }

    for(int i=2;i<=n;i++)
    {
        if(b[i]>0) tmp1+=b[i];
        else tmp2-=b[i];
    }
    ll fin;
    if(tmp1>tmp2)
        fin=tmp1;
    else fin=tmp2;//因为是+1或者-1这里的+1/-1直接省略掉不乘了
    printf("%lld\n%lld\n",fin,abs(tmp1-tmp2)+1);

    return 0;
}

【题解】差分——IncDec Sequence

下面是题目复述。

分析过程：

下面是AC代码。