题目描述

给定一个长度为 n 的数列 $a_1 , a_2 , … , a_n$ ，每次可以选择一个区间 [l,r]，使下标在这个区间内的数都加一或者都减一。

求至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列可能有多少种。

输入格式
第一行输入正整数 n。

接下来 n 行，每行输入一个整数，第 i+1 行的整数代表 $a_i$。

输出格式
第一行输出最少操作次数。

第二行输出最终能得到多少种结果。

数据范围
$0<n≤10^5,$
$0≤a_i<2147483648$

样例

输入样例

4
1
1
2
2

输出样例

1
2

其实呢，这道题既然涉及到了数组内区间全部加或减1

考的就是差分。

但问题在于，

表面上看差分好像解不出它想要的答案！！！

那么来给这道题做一下变形~

既然说到差分，就把这道题中的数组a变成它的差分数组b

（极具瞎试精神）

研究过差分的人就会发现

要把a数组中所有的数变得一样

其实就相当于把b数组中除第一位外其它位变成零。

而每次做加一的操作

就是把$b_l$加一，

再把$b_{r+1}$减一

做减一的操作

就是$b_l$减一，$b_{r+1}$加一

鉴于尽量不要背道而驰

我们希望每次的$b_l$和$b_{r+1}$加减一后比原先的值离零更近。

这时候，问题就变成了把b数组中的正数和负数配对。

然后每次把正数减一，负数加一

这时候题目给出的两种操作一定可以满足我们这个要求

当正数或负数被加或减光

从第二位开始全是零当然更好

如果不是,就可以把这些非零数和$b_1$或$b_n$进行操作

看到这里，总结一下：

只需要推一下数学公式就可以解决这道题

鉴于不需要考虑到底被减的是哪个正数或被加的是哪个负数

只需要把所有正数加到一起，把所有负数的绝对值加到一起，

得到pos和neg（分别是正数和负数的英文缩写）

反正两种操作可以满足所有情况

具体是什么情况就丢到九霄云外去吧！

对于题目的第一问，把正数和负数两两配对进行操作

需要用pos和neg中较小的那个那么多次操作~

然后，再加上两者的差，算是处理纯正或纯负的情况

（和$b_1$还是$b_n$操作，这一问还不用管）

其实，大家应该可以发现：较小的加上差不就是较大的吗？？？

简化一步总是好的

对于第二问，前面两两配对的操作最后只可能得到一种结果

（不管怎么配的对，都只会得到abs(pos-neg)那么多+1或-1）

真正出现分叉的是后面的纯正负结果

纯正负需要操作abs(pos-neg)次

这时候需要考虑每个有变化的地方是加还是减

算上全减得a[1]这种情况，总共可能出现abs(pos-neg)+1种情况

C++ 代码

#include<iostream>
#include<cmath>
using namespace std;
int c[100005];
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&c[i]);
    long long pos=0,neg=0;
    for(int i=n;i>1;i--){
        c[i]-=c[i-1];   //求差分
        if(c[i]>0)
            pos+=c[i];  //求差分数组中的正数和
        if(c[i]<0)
            neg-=c[i];  //求差分数组中的负数和
    }
    printf("%lld\n%lld",max(pos,neg),abs(neg-pos)+1);   //套用公式
    return 0;
}