【BZOJ1045】[HAOI2008] 糖果传递 贪心

【BZOJ1045】[HAOI2008] 糖果传递

Description

  有n个小朋友坐成一圈,每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。

Input

  第一行一个正整数n<=987654321,表示小朋友的个数.接下来n行,每行一个整数ai,表示第i个小朋友得到的
糖果的颗数.

Output

  求使所有人获得均等糖果的最小代价。

Sample Input

4
1
2
5
4

Sample Output

4

题解:面对环上的问题我们仍然考虑把环拆开

我们先不考虑n—1的传递,只考虑1—2—3。。—n的传递,此时有无脑贪心:

第i人向第i-1个人传递s[i-1]-(i-1)*ave个糖果,代价是s[i-1]-(i-1)*ave的绝对值,其中s是前缀和,ave是平均数

当1能向n传递时,假设传递的个数是x,则以后的所有i向i-1传递的数量都会减去x,但由于要取绝对值,所以如果s[i-1]-(i-1)*ave-x为正,则总代价会-x,若为负,则总代价会+x,那么最优情况肯定是是s[i-1]-(i-1)*ave-x中正数和负数的个数相等,即x取s[i-1]-(i-1)*ave的中位数(别忘了把0加上)

注意开long long

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
long long a[1000010],b[1000010];
long long n,ans,tot;
int main()
{
scanf("%lld",&n);
int i;
for(i=1;i<=n;i++) scanf("%lld",&a[i]),tot+=a[i];
tot/=n;
for(i=2;i<=n;i++) b[i]=b[i-1]+a[i]-tot;
sort(b+1,b+n+1);
for(i=1;i<=n;i++) ans+=abs(b[i]-b[n+1>>1]);
printf("%lld",ans);
return 0;
}
上一篇:Callable 和 Runnable 的区别


下一篇:【性能测试】jmeter的坑(1)——如何在多网卡情况下正确连接