博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
UVa11300 - Spreading the Wealth
阅读量:6502 次
发布时间:2019-06-24

本文共 979 字,大约阅读时间需要 3 分钟。

题意

n个人围成一圈,每个人都有一定数量的金币,金币总数可被n整除,现可将手中金币给左右相邻的人,最终使每人手中的金币数相等,求最少转移的金币数量。

思路

设a[i]给了a[i-1]x1个金币,从a[i+1]拿到x2个金币,则有

a1-x1+x2 = m (此时x1为给an的金币数) 另 c1 = a1 - m   则 x2 = x1 -c1

a2-x2+x3 = m ,则c2 = c1+a2-m   x3 = x1 - c2

...

|x1| + |x1-C1|+...+|x1-Cn-1|,要求这个最小,那么就是要x1为这些数的中位数

总结

学会数学分析的方法,总结规律并转换成代码

 

#include 
#include
#include
typedef long long LL;const int maxn = 1e6 + 5;LL a[maxn],c[maxn],tot,m; //数组a为每个人金币的数量 m为最后相等时的金币数using namespace std;int main(){ int n; while(scanf("%d",&n) == 1) { tot = 0; for(int i = 1; i <= n; i++) { cin >> a[i]; tot += a[i]; } m = tot / n; c[0] = 0; for(int i = 1; i < n; i++) { c[i] = c[i-1] + a[i] - m; } sort(c,c+n); LL x1 = c[n/2],ans = 0; for(int i = 0; i < n; i++) { ans += abs(x1 - c[i]); } cout << ans <

 

转载于:https://www.cnblogs.com/kikii233/p/5858230.html

你可能感兴趣的文章
mysql cte的好处_Mysql 8 重要新特性 - CTE 通用表表达式
查看>>
zcu106 固化_xilinx zcu106 vcu demo
查看>>
java ftpclient 代码_java后台代码ftpclient下载文件
查看>>
java mina 长连接_MINA实现TCP长连接(二)——服务端实现
查看>>
java数据库生成model_继承BaseModelGenerator 生成Model时添加数据库表字段 生成代码示例...
查看>>
https redirects java_java HttpURLConnection 得到 Redirect 转向的例子
查看>>
java读取html文件并替换_java读取html并替换相关内容
查看>>
java面向对象的概念_java面向对象(上)-- 面向对象的概念
查看>>
dbscan算法python实现_Python实现DBScan
查看>>
java智能聊天软件_Java使用青云客智能聊天接口做一个小助手
查看>>
java定义player类_Java自定义一个异常类NoThisSongException和Player类
查看>>
java 字符串 算法 面试题_java笔试手写算法面试题大全含答案
查看>>
java内部类访问外部类变量 final_Java内部类引用外部类中的局部变量为什么必须是final问题解析...
查看>>
java编程思想第四章_《JAVA编程思想》学习笔记——第四章 控制执行流程
查看>>
java 栈帧与类的关系_深入理解Java虚拟机之类运行时栈帧结构
查看>>
php中删除评论怎么做的,详解PHP如何实现评论回复删除功能
查看>>
macports 安装php,「macports」MacOS 中 MacPorts 安装和使用 - 金橙教程网
查看>>
php 审计 for linux,for linux是什么意思
查看>>
matlab里面连接器是什么,Oops - an error has occurred
查看>>
matlab建立桌面图标,在ubuntu16.04上创建matlab的快捷方式(实现方法)
查看>>