——>>設第i個人給了xi個cions自己左邊的人：則有 ——————————————>>x1 = x1 + 0; 第1人：a[1] - x1 + x2 = M；——>>x2 = x1 - (a[1]-M) 第2人：a[2] - x2 + x3 = M；——>>x3 = x1 - (a[1]-M) - (a[2]-M) …… 第n-1人：a[n-1] - x(n-1) + xn = M；——>>xn = x1 - (a[1]-M) - (a[2]-M) - ... - (a[n-1]-M)； 第n人：a[n] - xn + x1 = M；（這個沒用了） 設c[i] = c[i-1] + a[i] - M； 則有： ——>>x1 = x1 + c[0] ——>>x2 = x1 - c[1] ——>>x3 = x1 - c[2] …… ——>>x(n-1) = x1 - c[n]； 要求的便是| x1 | + | x1 + c[0] | + | x1 - c[1] | + ... + | x1 - c[n] |的最小值——>>中位數！ [cpp] #include <iostream> #include <algorithm> #include <cmath> using namespace std; const int maxn = 1000001 + 10; long long a[maxn], c[maxn]; //a[i]為輸入的第i個人的初始擁有資金，c[i]為 a[1]-M + a[2]-M + ... + a[i]-M int main() { int n, i; while(cin>>n) { long long sum = 0; //總和 for(i = 1; i <= n; i++) { cin>>a[i]; sum += a[i]; } long long M = sum / n; //求每人最後得到的錢 c[0] = 0; for(i = 1; i < n; i++) c[i] = c[i-1] + a[i] - M; sort(c, c+n); //從小到大排序，以便求得中位數 long long x1 = c[n/2]; //中位數的下標 sum = 0; //這次用sum來計算總交換的金幣數 for(i = 0; i < n; i++) sum += abs(x1 - c[i]); cout<<sum<<endl; } return 0; }
