糖果传递-阿里云开发者社区

开发者社区> 大数据> 正文
登录阅读全文

糖果传递

简介: 1045: [HAOI2008] 糖果传递http://www.lydsy.com/JudgeOnline/problem.php?id=1045 Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 1416  Solved: 658 [Submit][Status] Description 有n个小朋友坐成一圈,每人有ai个糖果

1045: [HAOI2008] 糖果传递
http://www.lydsy.com/JudgeOnline/problem.php?id=1045
Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 1416  Solved: 658
[Submit][Status]
Description
有n个小朋友坐成一圈,每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。

Input
小朋友个数n 下面n行 ai

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

Sample Input
4
1
2
5
4


Sample Output
4

数据规模
30% n<=1000
100% n<=1000000

 

微笑交换糖果的方式为:(人给人)1n21,32...nn-1.

ave为最终期望每人拥有的糖果数.

a[i]为第i个人拥有的糖果数,下标从1开始。

b[i]表示第i个人需要给第i-1个人的糖果数,允许为负。

假设第一个小朋友给第n个小朋友k个糖果,则

b[1]=k

a[1]-b[1]+b[2]=ave(原来的-送出的+新得到的=最终期望)得:

b[2]=b[1]-a[1]+ave;一般表达式为b[i]=b[i-1]-a[i-1]+ave;通项公式为:

b[i]=k- (求和(下标:1)(上标i-1(表达式:a[i]))+(i-1)*ave;

c[i]=(求和(下标:1)(上标i(表达式:a[i]))-i*ave;

b[i]=k-c[i-1];

显然有c[n]=0;b[1]=k=k+c[n];

总的代价为:求和(下标:1)(上标n(表达式:|b[i]| )

等于:求和(下标:1)(上标n(表达式:|k-c[i]| );

可转化为数轴上有n个点,求某点到其他所有点线段和的最小值。

故对c[]数组排序,找出中位数即可;若有偶数个,取中间两个任意一个都可以。

 

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
大数据
使用钉钉扫一扫加入圈子
+ 订阅

大数据计算实践乐园,近距离学习前沿技术

其他文章
最新文章
相关文章