题目:P4552 [Poetize6] IncDec Sequence - 洛谷

一道很有代表性的差分题。唉，写这到题的时候还把这道题给想复杂了，看来题解之后才恍然大悟

思路：要求最少次数的前提下，最终得到的数列有多少种。由于要对区域数组进行加减操作，所以可以首先想到差分实现区域加减，而对于这道题要我求将数组中的所有数都变为相同的数，那么就是让我们将差分数组变为除了首项其他项全部都为0。

那么我们该如何将除首项之外的其他项变为0呢？

首先，考虑到一次操作可以影响的位置有三种情况：

  1. 同时影响两个中间位置（2≤l≤r<n）：
    d[l]与 d[r+1]一个 +1，一个 -1。
    这两个位置都在 d[2]∼d[n]范围内，非常理想。

  2. 一端在 d[1]，另一端在中间（l=1 且 r<n）：
    d[1] 变，d[r+1] 反向变。
    这会顺便修改最终 d[1] 的值，同时清除一个中间位置的非零值。

  3. 一端在中间，另一端超出数组（l>1 且 r=n）：
    d[l] 变，而 d[n+1] 不存在，相当于只修改了一个中间位置。
    这也会顺便修改最终 a 的整体值，因为当 r=n 时，实际上只把 a[1]∼a[n] 都加了 1，这会改变差分数组的“尾部”。

  4. 两端分别是首尾（l=1,r=n）：
    只改 d[1]，不改任何中间位置，不直接帮助清零，只是整体平移。

最少操作次数

设 d[2]∼d[n]中：

  • 所有正数之和为 P

  • 所有负数的绝对值之和为 Q

每一次“理想操作”（第 1 类），可以让一个正数减 1，同时让一个负数加 1（绝对值减 1）。
这样一次操作就能让 P 和 Q 同时减 1。我们可以做 min⁡(P,Q)次这样的配对消除。

剩余的非零值要么全是正数（若 P>Q ），要么全是负数（若 Q>P ），总剩余量为 ∣P−Q∣。
这些剩余量已经无法在 d[2]∼d[n]内部两两抵消了，只能借助“边界”操作来一个个消除：

  • 用第 2 类操作（带 d[1]）

  • 或用第 3 类操作（带末尾之外）

每一步只能消掉一个单位的正数或负数，因此还需要 ∣P−Q∣ 步。

最少总操作次数 = min⁡(P,Q)+∣P−Q∣= max⁡(P,Q)。

最终数列的可能种数

在剩余 ∣P−Q∣ 步中，每一步我们可以选择是让 d[1] 参与，还是用“超出数组”的那一端。

  • 如果用 d[1]，那么 d[1] 的值会随之改变，最终 xx也会改变。

  • 如果用超出数组的一端，则 d[1] 不受影响。

也就是说，在这 ∣P−Q∣次额外操作里，我们可以任意选择其中 0∼∣P−Q∣ 次去修改 d[1]，其余的不改。
每次做出不同选择，最终的 x 就会不同。

因此，最终的 x（即最终相等的那个数）有：

∣P−Q∣+ 1

种不同的可能取值。

AC代码：时间复杂度 : O ( n )

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define int long long
#define endl '\n'

void solve() {
    int n;
    cin >> n;
    vector<ll> v(n + 1);
    vector<ll> d(n + 1);
    ll x = 0, y = 0;
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
        if (i != 1) d[i] = v[i] - v[i - 1];
        if (d[i] < 0) {
            x -= d[i];
        }
        else if(d[i]>0) {
            y += d[i];
        }
    } 
    cout << max(x, y) << endl;
    cout << abs(x - y) + 1 << endl;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _ = 1;
    //cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}