Luogu 🟢 P4552 [Poetize6] IncDec Sequence

題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 P4552 [Poetize6] IncDec Sequence

Problem Statement

題目簡述

給定一個長度為 $n$ 的數列 $a_1, a_2, \ldots, a_n$，每次可選擇一個區間 $[l, r]$ 將區間內所有數加 $1$ 或減 $1$。
求最少需要多少次操作才能使數列中所有數相等，以及在最少操作次數下，最終可能得到的數列有幾種。

Constraints

約束條件

• $1 \le n \le 100000$
• $0 \le a_i \le 2^{31}$

---

思路：差分思想

核心概念：區間操作轉化為單點操作

當題目涉及「區間加減」且最終目標與「相鄰元素的相對大小」有關時，差分陣列是首選的思考方向。

給定原數列，我們建構其差分陣列，其中每個元素等於原數列當前元素與前一個元素的差值。
目標是「使數列中所有數相等」，這等價於差分陣列中除了首項以外的所有元素都變成 $0$。

差分陣列的性質

對原數列的區間 $[l, r]$ 進行加 $1$ 或減 $1$ 的操作，反映在差分陣列上，只會改變兩個單點的值：

• 左邊界對應的差分值會增加或減少 $1$
• 右邊界下一個位置的差分值會減少或增加 $1$

也就是說，每次區間操作可以看作是選擇差分陣列中的兩個位置，一個加 $1$，另一個減 $1$。

操作分類與貪心策略

為了用最少的步驟將差分陣列（不含首項）全部歸零，我們可以將操作分為以下幾類：

1. 修改兩個都在範圍內的差分值：
   這會同時改變差分陣列中兩個有效位置的值。如果我們選擇一個正數和一個負數進行配對，一次操作就能讓兩個數都更接近 $0$。這是最高效的操作。
2. 修改首項與一個範圍內的差分值：
   這會改變原數列的首項，以及差分陣列中的一個位置。這相當於消耗一次操作來消除一個差分值，但會改變最終所有元素相等時的目標值。
3. 修改一個範圍內的差分值與一個超出範圍的值：
   這會改變差分陣列中的一個位置，以及一個超出範圍的位置。這同樣是消耗一次操作來消除一個差分值，但不會改變首項。

如何達到最少操作次數？

為了讓操作次數最少，我們應該盡可能多地使用第 1 類操作。

我們可以分別統計差分陣列中所有正數的總和與所有負數絕對值的總和，分別記做 $\textit{pos}$ 和 $\textit{neg}$。

• 透過第 1 類操作，我們最多可以進行這兩個總和中較小值次數的配對。
• 配對完後，差分陣列中只會剩下全為正數或全為負數的非零元素，其總和的絕對值為正負總和的差值。
• 這些剩下的非零元素，只能透過第 2 類或第 3 類操作來逐一消除，需要消耗與剩餘絕對值相等的次數。

因此，最少操作次數為：$\max(\textit{pos}, \textit{neg})$。

最終結果種類數

最終數列的所有元素都會等於首項。因此，最終結果的種類數，取決於首項有多少種可能的值。

在消除剩餘的 $|\textit{pos} - \textit{neg}|$ 個差分值時，我們可以自由選擇使用第 2 類操作或第 3 類操作：

• 每次使用第 2 類操作，都會使首項加 $1$ 或減 $1$。
• 每次使用第 3 類操作，首項保持不變。

假設我們在剩下的操作中，選擇了 $k$ 次第 2 類操作（$k$ 的範圍從 $0$ 到剩餘操作次數），那麼首項就會有 $|\textit{pos} - \textit{neg}| + 1$」種不同的變化結果。

複雜度分析

• 時間複雜度：$\mathcal{O}(n)$，只需遍歷一次陣列計算差分及正負總和。
• 空間複雜度：$\mathcal{O}(n)$，用於儲存輸入以及差分陣列。

---

Code

def solve():
    n = int(input())
    A = [int(input()) for _ in range(n)]

    # 建立差分陣列
    diff = [0] * n
    for i in range(1, n):
        diff[i] = A[i] - A[i - 1]

    # 統計差分陣列中正數與負數的總和
    pos = sum(diff[i] for i in range(n) if diff[i] > 0)
    neg = sum(-diff[i] for i in range(n) if diff[i] < 0)

    print(max(pos, neg))
    print(abs(pos - neg) + 1)


if __name__ == "__main__":
    solve()