@Gary-Ying
2018-10-15T09:49:01.000000Z
字数 1315
阅读 1080
解题报告
贪心
原题来自:HAOI 2008
有 个小朋友坐成一圈,每人有 颗糖果。每人只能给左右两人传递糖果。每人每次传递一颗糖果的代价为 1 。求使所有人获得均等糖果的最小代价。
对于 100% 的数据, ,保证答案可以用 64 位有符号整数存储。
设 表示第 个人向第 个人传递 颗糖果, 为 的平均数。
那么显然对于 ,都有 ,移项得
那么可以列出以下 个式子:
把后 个式子相加,可得:
即
可以看到,等式右边是 加上一个常数 ,所以
同理把后 个式子相加,可以得到
而题目求的是最小化 ,即
因为其中 均为常数,所以当 取 中位数时该式有最小值。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1000007;
int n, a[MAXN];
ll t[MAXN], ans, sum, ave;
inline void read(int &x){
int val=0; bool f=false; char ch=getchar();
while ((ch<'0'||ch>'9')&&(ch!='-')) ch=getchar();
if (ch=='-') f=true,ch=getchar();
while (ch>='0'&&ch<='9')val=(val<<3)+(val<<1)+ch-'0',ch=getchar();
x = f ? (-val) : val;
}
int main(){
read(n);
for (int i = 1; i <= n; ++i){
read(a[i]);
sum = sum + a[i];
}
ave = sum / n;
t[n] = 0;
for (int i = n - 1; i >= 1; --i)
t[i] = t[i+1] + a[i] - ave;
for (int i = 1; i <= n; ++i)
t[i] = -t[i];
sort(t + 1, t + 1 + n);
ans = 0;
for (int i = 1; i <= n; ++i)
ans = ans + abs(t[(n+1)/2] - t[i]);
printf("%lld\n", ans);
return 0;
}