题意概述
给定长度为 \(n\) 的数组 \(a\)，每次操作选择一个区间 \([l,r]\) 将 \(a\) 的所有元素加一或者减一。求最少操作次数使得 \(a\) 的每个元素相等，并求出在此前提下，有多少种不同的最终序列。
- 题目链接：增减序列
思路
设 \(d\) 为 \(a\) 的差分数组（从 \(1\) 开始），其中：
- \(d[1] = a[1]\)
- \(d[i] = a[i] - a[i-1]\)，\(2 \le i \le n\)
根据差分数组的定义，让 \(a\) 的全部元素相等等价于使 \(d[2,n]\) 都为 \(0\)，因此问题转换为使得 \(d[2,n]\) 全部为 \(0\) 的最小操作次数。
而对 \(a\) 的区间 \([l,r]\) 加 \(1\) 操作，也可转换为 \(d[l]\) 加 \(1\)，\(d[r+1]\) 减 \(1\)；减 \(1\) 操作转换为 \(d[l]\) 减 \(1\)，\(d[r+1]\) 加 \(1\)。
区间 \([l,r]\) 有 4 种选择策略：
- \(2 \le l \le r \le n\)；
- \(l = 1\)，\(2 \le r \le n\)；
- \(2 \le l \le n\)，\(r = n\)；
- \(l = 1\)，\(r = n\)。
要使 \(d[2,n]\) 全为 \(0\) 的操作次数最少，应尽可能使用策略 1，让正负数配对抵消。设 \(pos\) 为 \(d[2,n]\) 中所有正数之和，\(neg\) 为所有负数绝对值之和。用策略 1 可以配对 \(\min(pos, neg)\) 次，剩余 \(|pos - neg|\) 个单种符号，需要用策略 2 或策略 3 消去。
因此最少操作次数为：
\[\min(pos, neg) + |pos - neg| = \max(pos, neg)
\]
对于最终序列的种类数，根据差分定义，等价于当 \(d[2,n]\) 全为 \(0\) 时，\(a[1]\) 的不同取值数量。即在执行完策略 3 之后，策略 2 可以执行的最大次数：
\[|pos - neg| + 1
\]
参考例程如下：
#include <bits/stdc++.h>
using namespace std;
using ll = long long;int main() {int n;cin >> n;ll pos = 0, neg = 0;int last;cin >> last; for (int i = 1; i < n; i++) {int x;cin >> x;int d = x - last;if (d > 0) pos += d;else if (d < 0) neg -= d;last = x;}cout << max(pos, neg) << '\n';cout << abs(pos - neg) + 1 << '\n';return 0;
}