參考程序1:
#include <bits/stdc++.h>
using namespace std;
int main() {int N;cin >> N;vector<int> stones(N);int sum = 0;for (int i = 0; i < N; i++) {cin >> stones[i];sum += stones[i];}int target = sum / N; // 每個籃子的平均值int answer = INT_MAX; // 最終最小搬運次數// 枚舉所有可能的起點for (int start = 0; start < N; start++) {// 把圓圈旋轉,使 start 位置當作起點vector<int> rotated(N);for (int i = 0; i < N; i++) {rotated[i] = stones[(start + i) % N];}int moves = 0;vector<int> temp = rotated;// 按線性方式從左到右轉移石子for (int i = 0; i < N - 1; i++) {int diff = temp[i] - target; temp[i + 1] += diff; moves += abs(diff); }// 更新最小值answer = min(answer, moves);}cout << answer << endl;return 0;
}
參考程序2:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll; // 或者 using ll = long long;int main() {int N;cin >> N;vector<ll> a(N);ll sum = 0;for (int i = 0; i < N; ++i) {cin >> a[i];sum += a[i];}ll target = sum / N;// 構造前綴欠賬 S,包含 S0 = 0,一共 N 個值 S[0..N-1]vector<ll> S(N);S[0] = 0;for (int i = 1; i < N; ++i) {S[i] = S[i-1] + (a[i-1] - target);}// 找中位數(使用排序后直接取中間值)vector<ll> tmp = S;sort(tmp.begin(), tmp.end());ll median = tmp[N/2];// 計算最小步數:sum |S[i] - median|ll moves = 0;for (ll x : S) moves += llabs(x - median);cout << moves << '\n';return 0;
}