[关闭]
@Gary-Ying 2018-10-15T09:49:01.000000Z 字数 1315 阅读 1080

「一本通 1.1 练习 6」糖果传递

解题报告 贪心


题目描述

https://loj.ac/problem/10010

原题来自:HAOI 2008
个小朋友坐成一圈,每人有 颗糖果。每人只能给左右两人传递糖果。每人每次传递一颗糖果的代价为 1 。求使所有人获得均等糖果的最小代价。
对于 100% 的数据, ,保证答案可以用 64 位有符号整数存储。

题解

表示第 个人向第 个人传递 颗糖果, 的平均数。
那么显然对于 ,都有 ,移项得

那么可以列出以下 个式子:

把后 个式子相加,可得:

可以看到,等式右边是 加上一个常数 ,所以

同理把后 个式子相加,可以得到

而题目求的是最小化 ,即

因为其中 均为常数,所以当 中位数时该式有最小值。

代码

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int MAXN = 1000007;
  5. int n, a[MAXN];
  6. ll t[MAXN], ans, sum, ave;
  7. inline void read(int &x){
  8. int val=0; bool f=false; char ch=getchar();
  9. while ((ch<'0'||ch>'9')&&(ch!='-')) ch=getchar();
  10. if (ch=='-') f=true,ch=getchar();
  11. while (ch>='0'&&ch<='9')val=(val<<3)+(val<<1)+ch-'0',ch=getchar();
  12. x = f ? (-val) : val;
  13. }
  14. int main(){
  15. read(n);
  16. for (int i = 1; i <= n; ++i){
  17. read(a[i]);
  18. sum = sum + a[i];
  19. }
  20. ave = sum / n;
  21. t[n] = 0;
  22. for (int i = n - 1; i >= 1; --i)
  23. t[i] = t[i+1] + a[i] - ave;
  24. for (int i = 1; i <= n; ++i)
  25. t[i] = -t[i];
  26. sort(t + 1, t + 1 + n);
  27. ans = 0;
  28. for (int i = 1; i <= n; ++i)
  29. ans = ans + abs(t[(n+1)/2] - t[i]);
  30. printf("%lld\n", ans);
  31. return 0;
  32. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注