题目大意:n个人手中有些金币,每个人可给相邻两个人一些金币,使得最终每个人手中金币数相同,求被转手的金币最少数 m为最终每个人手中的金币数,a1,a2,a3,...,an为每个人开始时手中的金币数,x1,x2,x3,...,xn为每个人转手的金币数
- 假设 4个人 号分别为 1 2 3 4
x2 :为2号给1号的金币数
x3 :为3号给2号的金币数
x4 :为4号给3号的金币数
x1 :为1号给4号的金币数
设:c1 = a1 - m(即:cn = an - m);
C1 = c1 = a1 - m;
C2 = c1 + c2 = C1 + c2 = C1 + a2 - m;
C3 = c1 + c2 + c3 = C2 + c3 = C2 + a3 - m;
...
Cn = C(n - 1) + an - m;
1号 :m = a1 + x2 - x1; x2 = m + x1 - a1 = x1 - c1 = x1 - C1;(1号最终所得金币为其原有的金币加上2号所给的减去其给4号的金币所得,下面同理)
2号 :m = a2 + x3 - x2; x3 = m + x2 - a2 = x2 - c2 = x1 - c1 - c2 = x1 - C2;
3号 :m = a3 + x4 - x3; x4 = m + x3 - a3 = x3 - c3 = x1 - c1 - c2 - c3 = x1 - C3;
...
xn = x1 - C(n - 1);
求转手金币的最小值(即求x1 + x2 + x3 +...+xn的最小值即求x1+|x1-C1|+|x1-C2|+|x1-C3|+...+|x1-C(n-1)|的最小值)
其几何意义为求一个点到n个点距离和的最小值(即数轴上点x1到Ci的距离和的最小值)
若想使其距离和最小,则x1需满足的条件是:点x1必须为n个点中的中位数
若点数n为奇数则点x1必须与中间那个点重合(即中位数)
若点数n为偶数则点x1必须在中间两个点之间(仍是中位数) #include<stdio.h>
#include<math.h>
#include<stdlib.h>
#define N 1000010 long long a[N], c[N], sum, ans, m, x1;
int cmp(const void *a, const void *b)
{
return *(int *)a - *(int *)b;
} int main()
{
int n, i;
while(scanf("%d", &n) != EOF)
{
sum = ans = ;
for(i = ; i < n ; i++)
{
scanf("%lld", &a[i]);
sum += a[i];
}
m = sum / n;
c[] = ;
for(i = ; i < n ; i++)
c[i] = c[i - ] + a[i] - m;
qsort(c, n, sizeof(c[]), cmp);
x1 = c[n / ];
for(i = ; i < n ; i++)
ans += fabs(x1 - c[i]);
printf("%lld\n", ans);
}
return ;
}
UVA 11300 Spreading the Wealth的更多相关文章
-
UVa 11300 Spreading the Wealth(有钱同使)
p.MsoNormal { margin: 0pt; margin-bottom: .0001pt; text-align: justify; font-family: "Times New ...
-
uva 11300 - Spreading the Wealth(数论)
题目链接:uva 11300 - Spreading the Wealth 题目大意:有n个人坐在圆桌旁,每个人有一定的金币,金币的总数可以被n整除,现在每个人可以给左右的人一些金币,使得每个人手上的 ...
-
UVA.11300 Spreading the Wealth (思维题 中位数模型)
UVA.11300 Spreading the Wealth (思维题) 题意分析 现给出n个人,每个人手中有a[i]个数的金币,每个人能给其左右相邻的人金币,现在要求你安排传递金币的方案,使得每个人 ...
-
数学/思维 UVA 11300 Spreading the Wealth
题目传送门 /* 假设x1为1号给n号的金币数(逆时针),下面类似 a[1] - x1 + x2 = m(平均数) 得x2 = x1 + m - a[1] = x1 - c1; //规定c1 = a[ ...
-
UVA - 11300 Spreading the Wealth(数学题)
UVA - 11300 Spreading the Wealth [题目描述] 圆桌旁边坐着n个人,每个人有一定数量的金币,金币的总数能被n整除.每个人可以给他左右相邻的人一些金币,最终使得每个人的金 ...
-
Uva 11300 Spreading the Wealth(递推,中位数)
Spreading the Wealth Problem A * regime is trying to redistribute wealth in a village. They ...
-
UVA 11300 Spreading the Wealth (数学推导 中位数)
Spreading the Wealth Problem A * regime is trying to redistribute wealth in a village. They ...
-
Math - Uva 11300 Spreading the Wealth
Spreading the Wealth Problem's Link ---------------------------------------------------------------- ...
-
[ACM_几何] UVA 11300 Spreading the Wealth [分金币 左右给 最终相等 方程组 中位数]
Problem A * regime is trying to redistribute wealth in a village. They have have decided to ...
-
UVa 11300 Spreading the Wealth 分金币
圆桌旁坐着 n 个人,每个人都有一定数量的金币,金币总数能够被 n 整除.每个人可以给他左右相邻的人一些金币,最终使得每个人的金币数目相等.你的任务是求出被转手的金币数量的最小值,比如 n = 4, ...
随机推荐
-
C# 对List<;T>;取交集、连集及差集
1. 取交集 List A :{1,5,9,3,7} List B:{1,6,8,5,3,2,9,4} var intersectedList = listA.Intersect(listB, new ...
-
ASP.NET State Service服务
ASP.NET State Service服务是用来管理 Session 的,正常来说,Session 位于IIS进程中(其实可以理解成在服务器的内存中),当IIS重启或程序池回收会自动清空Sessi ...
-
create a new table for the query results
http://*.com/questions/2698401/how-to-store-mysql-query-results-in-another-table CREATE ...
-
linux安装MongoDB
安装 32bit的mongodb最大只能存放2G的数据,64bit就没有限制 到官网,选择合适的版本下载,本次下载3.4.0版本 解压 tar -zxvf mongodb-linux-x86_64-u ...
-
Android -- 再来一发Notification
之前写过一个Notificaiton的文章,用上面的方式去操作也是OK的,但是到后面的SDK之后,有些方法被弃用,甚至我到SDK23的时候,我发现有些方法直接没了,所以在这里重新写一下最新的用法. h ...
-
文件解压缩 tar zip
zip -e var-log-protected.zip /var/log/* Enter password: Verify password: updating: var/log/acpid (de ...
-
nmap常用参数
总结: 主机发现 -sn 防止NMAP端口扫描 -SP TCP 半连接扫描,默认是通过80端口来发现主机的 -SA ACK ping 扫描 -SU UDP ping 扫描 不好 ...
-
android控件拖动,移动、解决父布局重绘时控件回到原点
这是主要代码: 保证其params发生改变,相对于父布局的位置就能达到位置移动到原来的位置 // 每次移动都要设置其layout,不然由于父布局可能嵌套listview,当父布局发生改变冲毁(如下拉刷 ...
-
UITableView去掉分隔符
或用代码实现 [TableView setSeparatorColor:[UIColor clearColor]]; 问题一用你给的方法貌似不行,我用这个方法把分隔线给“去掉”了: [editV ...
-
PL/SQL developer 出现无效的SQL语句的解决
这里要说的SQL语句本身没有错误,但是PL/SQL developer 出现无效的SQL语句的解决. 出现这个提示是因为下面的这句代码: --变量num:是一个地址值,在该地址上保存了输入的值 acc ...