分金币 [CQOI 2011] [BZOJ 3293]
Description
圆桌上坐着n个人,每人有一定数量的金币,金币总数能被n整除。每个人可以给他左右相邻的人一些金币,最终使得每个人的金币数目相等。你的任务是求出被转手的金币数量的最小值。
Input
第一行为整数n(n>=3),以下n行每行一个正整数,按逆时针顺序给出每个人拥有的金币数。
Output
输出被转手金币数量的最小值。
Sample Input
4
1
2
5
4
Sample Output
4
HINT
设四个人编号为1,2,3,4。第3个人给第2个人2个金币(变成1,4,3,4),第2个人和第4个人分别给第1个人1个金币。
N<=<=100000,总金币数<=10^9
Solution
贪心来看,对于每个人和他右手边的小伙伴,要么这个人给小伙伴金币,要么小伙伴给这个人两个人不可能互相传递,因为如果有这样的操作存在,两人互相抵消影响,这样答案肯定更优假设第i个人原有ai枚金币,向他右手边的小伙伴递了bi枚金币(为负数说明拿了-bi枚)那么可以列出n个方程看似是一个n元一次方程组,其实有一个方程是多余的,n个方程左右相加就看出来了= =
也就是说,我们现在有n个未知数和n - 1个方程,没办法求出所有未知数,但是初中老师教育过我们。这东西还是能够表示出任意两个变量的关系的随意去掉第i个方程,剩下n - 1个方程左右相加,整理一下,,这里g是所有金币的平均值,也就是每个人最后要拥有的金币数量假设我们知道bn,那所有剩下的bi都能写成bn + k的形式,利用上式递推即可
我们的目的,是让最小,现在能用一个单一变量bn表示出所有bi,假设把这样的所有k放到一条数轴上,|bn - ki|的几何意义就是bn到ki的距离了。怎么让这样的距离和最小?取个中位数即可。
Code
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; typedef long long LL;
const int maxn = 1E5 + ; int n,tot,g,a[maxn];
LL Ans,dt[maxn]; int main()
{
cin >> n;
for (int i = ; i <= n; i++)
scanf("%d",&a[i]),tot += a[i];
g = tot / n;
for (int i = n - ; i; i--)
dt[i] = dt[i+] - 1LL*(a[i+] - g);
sort(dt + ,dt + n + );
int mid = ( + n) >> ;
for (int i = ; i <= n; i++)
Ans += 1LL*abs(dt[mid] - dt[i]);
cout << Ans;
return ;
}
最新文章
- 利用gulp解决前后端分离的header/footer引入问题
- office2010里怎么设置页码为第几页共几页
- 【C++沉思录】代理类
- SQL Server Reporting Services – Insufficient Rights Error
- Android 自定义RadioButton实现
- guestfish 修改 image file
- html5游戏开发--";动静";结合用地图块拼成大地图 &; 初探lufyl
- 2.10. 代码片段:demo方法(Core Data 应用程序实践指南)
- vue实现淘宝购物车功能
- modelform save
- 使用jquery-form进行文件上传
- 【Jmeter自学】Jmeter性能测试报告(八)
- odoo 默认显示字段
- Thunder团队Alpha周贡献分规则及贡献分分配结果
- 【Asp.net入门5-01】SportsStore:一个真实的应用程序
- 数据适配:DataAdapter对象概述
- JPA 入门程序及相关注解
- Kotlin Android Studio 环境搭建
- Oracle分组函数实例
- 新学一招,使用热门的Git