首页 > 代码库 > bzoj 1045: [HAOI2008] 糖果传递 贪心
bzoj 1045: [HAOI2008] 糖果传递 贪心
1045: [HAOI2008] 糖果传递
Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 1812 Solved: 846
[Submit][Status]
Description
有n个小朋友坐成一圈,每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。
Input
小朋友个数n 下面n行 ai
Output
求使所有人获得均等糖果的最小代价。
Sample Input
4
1
2
5
4
1
2
5
4
Sample Output
4
数据规模
30% n<=1000
100% n<=1000000
数据规模
30% n<=1000
100% n<=1000000
HINT
Source
http://www.cnblogs.com/wmrv587/p/3900279.html
突然发现做题是把模型简化是非常好的思路。
#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>using namespace std;#define MAXN 1000100typedef long long qword;qword num[MAXN],f[MAXN];int main(){ freopen("input.txt","r",stdin); int n; scanf("%d",&n); int i,j,k; qword sum=0; for (i=0;i<n;i++) { scanf("%lld",&num[i]); sum+=num[i]; } int base=sum/n; int x,y,z; f[0]=num[i]-base; for (i=1;i<n;i++) { f[i]=f[i-1]+num[i]-base; } sort(f,&f[n]); int mid=(n-1)/2; qword ans=0; for (i=0;i<n;i++) { ans+=abs(f[i]-f[mid]); } printf("%lld",ans); return 0;}
bzoj 1045: [HAOI2008] 糖果传递 贪心
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。