解題思路
假設每個人向左傳遞 c[i]（其中 c[1] 表示第一個人向最后一個人傳遞），則 c[i] 的絕對值之和為傳遞的最小次數，每個人的初始值為 a[i] ，最終值為 ave（sum/n），則 ave=a[i]-c[i]+c[i+1] ，
處理 a[i]=a[i]-ave ，上式變為 c[i+1]=c[i]-a[i] ，
于是，求 c[i] 的絕對值之和最小值問題轉化成了：（貨倉選址問題）給定數軸上的n個點，找出一個到它們的距離之和盡量小的點，這個點就是這些數的中位數，
解題步驟
1.a[i]=a[i]-ave，c[i+1]=c[i]-a[i]
2.對 c[i] 排序，取中位數
實體題解
均等筆
題目描述
n 個人圍成一圈，每人有 ai 支筆，每人可以向左右相鄰的人傳遞筆，每人每次傳遞一支筆消耗的能量為 1，
求使所有人獲得均等數量的筆的最小能量，輸入格式
第一行一個整數 n ，表示人的個數（30%的資料，n<=1000；100%的資料，n<=1e6），
接下來 n 行，每行一個整數 ai ，輸出格式
輸出一個整數，表示使所有人獲得均等筆的最小能量，（答案保證可以用64位有符號整數存盤）
完整代碼
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
int a[1000010], c[1000010];
int main()
{
int n, i;
long long ans = 0, ave = 0;
scanf("%d", &n);
for (i = 0; i < n; i++) {
scanf("%d", &a[i]);
ave += a[i];
}
ave /= n;
for (i = 0; i < n; i++) {
a[i] -= ave;
}
for (i = 1; i <= n; i++) {
c[i] = c[i - 1] - a[i - 1];
}
sort(c + 1, c + 1 + n);
for (i = 1; i <= n; i++) {
ans += abs(c[i] - c[n / 2]);
}
printf("%lld", ans);
return 0;
}
參考資料：糖果傳遞（中位數、環形均分紙牌）
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/47160.html
標籤：C
下一篇：C語言學習(1)