題目描述
有N堆紙牌，編號分別為 1,2,…,N。每堆上有若干張，但紙牌總數必為N的倍數。可以在任一堆上取若干張紙牌，然后移動。
移牌規則為：在編號為1堆上取的紙牌，只能移到編號為2的堆上；在編號為N的堆上取的紙牌，只能移到編號為N?1的堆上；其他堆上取的紙牌，可以移到相鄰左邊或右邊的堆上。
現在要求找出一種移動方法，用最少的移動次數使每堆上紙牌數都一樣多。
例如N=4，4堆紙牌數分別為：
①9②8③17④6
移動3次可達到目的：
從 ③ 取4張牌放到 ④ （9,8,13,10）-> 從 ③ 取33張牌放到 ②（9,11,10,10）-> 從 ② 取11張牌放到①（10,10,10,10）。
輸入格式
兩行
第一行為：NN（NN 堆紙牌，1≤N≤100）
第二行為：A1,A2,…,An（N堆紙牌，每堆紙牌初始數，1≤Ai≤100001≤Ai?≤10000）
輸出格式
一行：即所有堆均達到相等時的最少移動次數。
輸入數據 1
4
9 8 17 6
輸出數據 1
3
根據題目描述，我們需要將所有堆的紙牌數量調整為相等，并且要求移動次數最少。通過分析可以發現，每個非目標值的堆都需要至少一次移動來調整其數量，因此最少移動次數等于需要調整的堆的數量減一（當相鄰堆都需要調整時，可以合并移動）。
以下是解決該問題的 C++ 代碼：
#include <iostream>
#include <vector>
using namespace std;
int main()
{int n;cin >> n;vector<int> cards(n);int sum = 0;for (int i = 0; i < n; i++) {cin >> cards[i];sum += cards[i];}int avg = sum / n;for (int i = 0; i < n; i++) {cards[i] -= avg;}vector<int> prefix(n);prefix[0] = cards[0];for (int i = 1; i < n; i++) {prefix[i] = prefix[i-1] + cards[i];}int count = 0;for (int i = 0; i < n; i++) {if (prefix[i] != 0) {count++;}}cout << count << endl;return 0;
}代碼說明：
- 輸入處理：首先讀取堆數
n，然后讀取每堆的紙牌數量并計算總和。 - 計算平均值：總和除以堆數得到每堆應有的紙牌數量。
- 調整數組：將每堆的紙牌數量轉換為與平均值的差值。
- 前綴和數組：計算調整后數組的前綴和，前綴和中的每個元素表示從第一堆到當前堆的總差值。
- 統計非零元素：前綴和數組中非零元素的數量即為最少移動次數。
該算法的時間復雜度為 O (n)，能夠高效處理題目給定的數據范圍。
讓我們通過逐步拆解問題和代碼邏輯，深入理解如何通過前綴和數組的非零元素數量確定最少移動次數。
一、問題本質分析
- 核心矛盾：每堆紙牌數與平均值的差異需要通過移動消除。
- 移動規則：每次移動只能影響相鄰堆，且移動方向受限（如堆 1 只能移到堆 2）。
- 關鍵觀察：
- 若某堆的紙牌數與平均值的差為
d，則必須通過移動d張紙牌到相鄰堆來平衡。 - 每次移動可以消除一個累積的不平衡（即前綴和中的非零值）。
- 若某堆的紙牌數與平均值的差為
二、代碼邏輯詳解
1. 輸入處理與平均值計算
int n;
cin >> n;
vector<int> cards(n);
int sum = 0;
for (int i = 0; i < n; i++) {cin >> cards[i];sum += cards[i];
}
int avg = sum / n;
- 輸入處理：讀取堆數
n和每堆的初始紙牌數。 - 平均值計算：總和
sum除以堆數n得到目標值avg。若紙牌總數不是n的倍數，題目保證輸入合法，因此無需處理。
2. 調整數組（差值數組）
for (int i = 0; i < n; i++) {cards[i] -= avg;
}
- 差值數組：將每堆的紙牌數轉換為與平均值的差值。例如，若某堆初始有 9 張，平均值為 10，則差值為
-1，表示需要移入 1 張紙牌。
3. 前綴和數組構造
vector<int> prefix(n);
prefix[0] = cards[0];
for (int i = 1; i < n; i++) {prefix[i] = prefix[i-1] + cards[i];
}
- 前綴和的意義：
prefix[i]表示從第 1 堆到第i堆的總差值。例如，若前 3 堆的差值分別為-1, -2, 7，則prefix[2] = -1 + (-2) + 7 = 4，表示前 3 堆總共多出 4 張紙牌，需要后續堆來平衡。
4. 統計非零元素數量
int count = 0;
for (int i = 0; i < n; i++) {if (prefix[i] != 0) {count++;}
}
cout << count << endl;
- 移動次數的來源：前綴和數組中的每個非零元素代表一個必須進行的移動步驟。例如：
- 若
prefix[i]為正，表示前i堆需要移出prefix[i]張紙牌； - 若為負，表示前
i堆需要移入abs(prefix[i])張紙牌。 - 每次移動可以消除一個非零的前綴和值，因此非零元素的數量即為最少移動次數。
- 若
三、數學證明與示例驗證
1. 數學證明
- 前綴和的性質：
由于所有堆的總差值為 0（總和為sum - n*avg = 0），前綴和數組的最后一個元素prefix[n-1]必為 0。 - 移動次數的推導：
假設前綴和數組中有k個非零元素，每次移動可以消除一個非零值（例如，將prefix[i]的不平衡轉移到下一堆），最終所有前綴和都變為 0，因此需要k次移動。
2. 示例分析（輸入：4 9 8 17 6）
- 步驟 1：計算平均值
sum = 9+8+17+6 = 40，avg = 40/4 = 10。 - 步驟 2：構造差值數組
cards = [9-10, 8-10, 17-10, 6-10] = [-1, -2, 7, -4]。 - 步驟 3：計算前綴和數組
prefix[0] = -1prefix[1] = -1 + (-2) = -3prefix[2] = -3 + 7 = 4prefix[3] = 4 + (-4) = 0
非零元素為-1, -3, 4，共 3 個，對應移動次數 3。
3. 移動過程與前綴和的關系
- 第一次移動：從堆 3 移 4 張到堆 4。
差值數組變為[-1, -2, 3, 0]，前綴和變為[-1, -3, 0, 0]。此時非零元素減少 1 個。 - 第二次移動：從堆 3 移 3 張到堆 2。
差值數組變為[-1, 1, 0, 0]，前綴和變為[-1, 0, 0, 0]。非零元素再減少 1 個。 - 第三次移動：從堆 2 移 1 張到堆 1。
差值數組全為 0，前綴和全為 0。移動次數為 3。
四、時間復雜度分析
- 輸入處理：O(n)
- 平均值計算：O(1)
- 差值數組構造：O(n)
- 前綴和數組構造：O(n)
- 非零元素統計：O(n)
- 總時間復雜度：O (n)，可高效處理題目給定的
n≤100的數據規模。
五、關鍵思想總結
- 差值數組：將問題轉化為消除各堆與平均值的差異。
- 前綴和數組：將全局的移動需求轉化為局部的累積不平衡。
- 貪心策略：每次移動消除一個累積的不平衡，非零前綴和的數量即為最少移動次數。
通過這種方法，我們無需模擬具體的移動過程，而是通過數學分析直接得出最優解，體現了算法設計中的抽象思維和問題轉化能力。
![Matrix Theory study notes[6]](http://pic.xiahunao.cn/Matrix Theory study notes[6])
