题目描述

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

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

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

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

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

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

数据范围
0<n≤105,
0≤ai<2147483648

样例

输入样例：
4
1
1
2
2
输出样例：
1
2

算法1

差分

差分的定义:
    原数组 a[1] a[2] a[3] ... a[n]
    差分数组 b[1] = a[1] b[2] = a[2] - a[1] b[3] = a[3] - a[2] ... b[n] = a[n] - a[n - 1]
    差分数组求前缀和就是原数组

差分的用途：
    在原数组[l, r]区间上同时加上一个数c，只需要对差分数组 b[l] += c, b[r + 1] -= c
    然后对其求前缀和，可得加完后的数组

思路：
    每次操做只能在区间同时加1或减1，最后都变成同一个数
    选取一个区间[i, j] b[i] ++ b[j + 1] -- 或 b[i] -- b[j + 1] ++ 两操作异号
    使b[2] ~ b[n] 全变成0，所有数就和b[1]一样了

    i 和 j 的选择有四种情况
    1. i >= 2, j <= n
    2. i = 1, j <= n
    3. i >= 2. j = n + 1
    4. i = 1, j = n + 1 (无意义)

    在差分数列中 找两个异号的数优先进行第1种操作，最快到达0
    但是所有正数和负数的和可能不为0，这里就要进行第2或第3种操作
    改变b[1]的值，所以最终能得到多少种结果就是进行多少组的第2和第3种操作
    例如：最后正数和负数之和等于5
    则有：第2种操作：0, 1, 2, 3, 4, 5
          第3种操作：5, 4, 3, 2, 1, 0
    一种6种情况

    p是所有正数的和，q是abs(所有负数的和) 
    所以最少操作次数 = min(q, p) + abs(q - p) = max(q, p)
    最终能得到多少种结果 = abs(p - q) + 1

C++ 代码

#include <iostream>

using namespace std;

const int N = 100010;
typedef long long LL;

int n;
int a[N], b[N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) b[i] = a[i] - a[i - 1]; // 求差分数组

    LL pos = 0, neg = 0;
    for (int i = 2; i <= n; i++)
    {
        if (b[i] > 0) pos += b[i];
        else neg -= b[i]; // 负数用-=
    }

    cout << min(pos, neg) + abs(pos - neg) << endl;
    cout << abs(pos - neg) + 1 << endl;
}