1045: [HAOI2008] 糖果传递
2024-08-24 09:30:55
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 4897 Solved: 2457
[Submit][Status][Discuss]
Description
有n个小朋友坐成一圈,每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。
Input
第一行一个正整数nn<=1'000'000,表示小朋友的个数.
接下来n行,每行一个整数ai,表示第i个小朋友得到的糖果的颗数.
Output
求使所有人获得均等糖果的最小代价。
Sample Input
4
1
2
5
4
1
2
5
4
Sample Output
4
毕业被班上委托制作学校录取分布地图。。。没钱拿(눈_눈),我的时间可是10美刀/小时
和均分纸牌类似,以绝对值差为贪心原则
设每位小朋友有Ai颗糖,若Xi>0表示第i位小朋友向第i-1位小朋友传递Xi颗糖,若Xi<0表示第i-1位小朋友向第i位小朋友传递Xi颗糖
最终每位小朋友持有ave=(A1+A2...+An)/n颗糖
则:
A1-X1+X2=ave——>X2=X1-(A1-ave)=X1-C1——>C1=A1-ave
A2-X2+X3=ave——>X3=X2-(A2-ave)=X1-C2——>C2=C1+A2-ave
A3-X3+X4=ave——>X4=X3-(A3-ave)=X1-C3——>C3=C2+A3-ave
......
An-Xn+X1=ave——>Xn=Xn-1-(An-ave)=X1-Cn——>Cn=Cn-1+An-ave
于是ans=|X1-C1|+|X2-C2|+|X3-C3|+...+|Xn-Cn|
为了使ans最小,Xi应该最接近Ci的平均数
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std; #define LL long long const int MAXN=; LL n,mid,ave,ans;
LL A[MAXN],C[MAXN]; int main()
{
cin>>n;
for(int i=;i<=n;i++)
{
cin>>A[i];
ave+=A[i];
}
ave/=n;
for(int i=;i<=n;i++)
C[i]=C[i-]+A[i]-ave;
sort(C+,C+n+);
mid=C[n/+];
for(int i=;i<=n;i++)
ans+=abs(C[i]-mid);
cout<<ans<<endl;
return ;
}
最新文章
- jQuery中json对象与json字符串互换
- HashMap 遍历
- 北大poj-1091
- HDU 4876 ZCC loves cards(暴力剪枝)
- Event Managers
- Printing Architecture
- 高性能 TCP &;amp; UDP 通信框架 HP-Socket v3.2.3 正式宣布
- HDU 3925 Substring 【大数相减】
- JUnit使用参数测试和一组测试
- webpack入门必知必会
- web工程师经常遇到的专业术语(待补充)
- Fum uc M-R ko P&#39;s R
- django模板引擎自定义变量
- android实用软件tasker应用设置
- 与我们息息相关的internet服务(3)---电子邮件服务
- Unity3D_UGUI判断鼠标或者手指是否点击在UI上
- c# 设置桌面背景窗口 SetParent
- 题解——洛谷P3812【模板】线性基
- Java与GIS的联系
- kali下利用weeman进行网页钓鱼