“代码特别短，心路历程特别长” – 啊，我死了~~

思路：差分 + 贪心

题目理解：经过多少次操作使得 a1 = a2 = a3 = … = an,且这种数列有多少种

分析：

1. 现构造差分数组b[], 使得 b1=a1,b2=a2-a1,b3=a3-a2 … $ b_n $ = $ a_n $ - $ a_{n-1} $ ,
2. 即满足题目要求的 b[] 为 $ b_2 $ ~ $ b_n $ = 0, $ b_1 $ 任意

3. 题目转化为：1.至少操作多少次可使$ b_2 $ ~ $ b_n $ = 0, 2. b1 有多少种值（代表了a[] 有多少种情况）

4. 我们可以发现： $ a_L$ ~ $ a_R $ 这一段区间内加一或者减一 等价于 $ b_L $ += 1 , $ b_{R+1} $ -= 1;（可以看到差分数组b[] 会比 原数组a[] 多操作一个数 $ a_R $ ，$ b_{R+1} $）

5. 可以把 对a[] 操作的区间分为以下四类(L 是区间左端点，R是右端点)：
   • 下标1 ~ n 区间加1或者减1 — 无意义，因为对a[] 整体加1或减1，它们的差值不会变
   • L = 1 ，R <= n-1 对应于 $b_1$+1/-1, $b_2$ ~ $b_n$ 中某个数-1/+1;
   • 2 <= L，R = n 对应于 $b-{n+1}$ +1/-1 , $b_2$ ~ $b_n$ 中某个数-1/+1;
   • 2 <= L <= R <= n-1 对应于 在$b_2$ ~ $b_n$ 中 另某一个数 + 1， 另一个数 -1；
   • 所以，直观一点，贪心一点，先用第4类操作，可以改变两个正负的b，余下的b全是正/负，再用对应的 第2类或第3类操作改变它
   • 注：p:差分数组中正数的和，q: 差分数组中负数绝对值的和
   • 得出结论：1.操作次数：min{p,q] + |p -q| = max{p,q}; 2. 对应的不同情况个数：|p - q| + 1

代码：

#include <iostream>

using namespace std;

typedef long long LL;

const int N = 100010;

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]; // 利用原数组a[] 构造差分数组b[]

    LL p=0,q=0; // p 正数的和 q:负数绝对值的和
    for(int i=2;i<=n;i++)
        if(b[i] > 0) p +=b[i];
        else q -= b[i];

    cout << max(p,q) << endl;
    cout << abs(p-q) + 1 << endl;

    return 0;
}

啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊