uva 11300 Spreading the Wealth_数学推倒 + 思维
这道题和负载平衡问题是同一道题, 如果 $n <= 100$ 的话是可以用最小费用流来求解的。
但是题中 $n$ 最大可达到 $10^6$, 这就需要我们进行一些性质分析与推导。
首先, 我们设每个·人手里最终金币数为 $C$
设 $X_{i}$ 为第 $i$个人给第 $i+1$ 个人的金币数目, 这个数目可以为负(第$i + 1$ 个人向左给了第$i$ 个人$|X_{i}|$个。
则我们不难发现:
1. $A_{2}+X_{1}-X_{2}=C$
2. $A_{3}+X_{2}-X_{3}=C$
3. $A_{4}+X_{3}-X_{4}=C$
4. ...
5. $A_{i}+X_{i-1}-X_{i}=C$
而这道题要求的其实就是$min|X_{1}| + |X_{2}| + |X_{3}| + |X_{4}| +... |X_{n}|$
那么,我们可将上面的等式进行变形,得:
1. $X_{1} = X_{1}$
2. $X_{2} =A_{2}-C+X_{1}$
3. $X_{3} =A_{2} + A_{3}-2*C+X_{1}$
4. $X_{4} =A_{2} + A_{3} +A_{4}-3*C+X_{1}$
5. $X_{5} =A_{2}+A_{3}+A_{4}+A_{5}-4*C+X_{1}$
此时,相信聪明的读者们不难发现规律:
$X_{i} = \sum\limits_{k=2}^i-(i-1)*C+X_{1}$ 即 $X_{i} = \sum\limits_{k=2}^i-(i-1)*C-(-X_{1})$
我们可以把$X_{1}$抽象成数轴上的一个点, 我们设$g_{i}= \sum\limits_{k=2}^i-(i-1)*C$,那么我们希望 $X_{1}$ 到所有 $g_{i}$ 的距离和最短,这个 $X_{i}$ 一定是 $g_{i}$中的中位数,于是我们将所有的 $g_{i}$ 排序,取中位数作为 $X_{1}$ 即可,我们也就能顺便推出所有的 $X_{i}$ ,最后加和即可,总时间复杂度为 $O(nlogn)$
最新文章
- Appium环境搭建+cordova
- 利用CSOM向列表添加文件夹
- (转)HTTP长连接和短连接
- centos7.0改变用户创建目录组权限
- CentOS6设置密码过期时间
- JS中 toString() &; valueOf()
- android 下滤镜效果的实现
- Asp.Net 之 Web.config下Authorization节点
- linux编译注解
- $cordovaDialogs使用时遇到的问题
- js获取某个标签中的信息
- notepad扩展搜索,正则搜索
- app中rem算法
- java面试一、1.4锁机制
- Intelij IDEA 内置 sql gui
- Spring消息中间件ActiveMQ
- SOA架构父工程的pom配置
- JAVA第五周 动手动脑
- toFixed()与toPrecision()
- OSG选取点云坐标不准的解决办法
热门文章
- mysql备份脚本二(带日志)
- HDU1846 - Brave Game【巴什博弈】
- 洛谷P1046 陶陶摘苹果
- bzoj 2834: 回家的路
- 【SPOJ 104】HIGH - Highways (高斯消元)
- 【Manthan, Codefest 18 (rated, Div. 1 + Div. 2) B】Reach Median
- (3)Spring Boot热部署【从零开始学Spring Boot】
- 洛谷—— P1189 SEARCH
- POJ 1811
- spring batch(一):基础部分