Problem
A Communist regime is trying to redistribute wealth in a village. They have have decided to sit everyone around a circular table. First, everyone has converted all of their properties to coins of equal value, such
that the total number of coins is divisible by the number of people in the village. Finally, each person gives a number of coins to the person on his right and a number coins to the person on his left, such that in the end, everyone has the same number of
coins. Given the number of coins of each person, compute the minimum number of coins that must be transferred using this method so that everyone has the same number of coins.
The Input
There is a number of inputs. Each input begins withn(n<1000001), the number of people in the village.nlines follow, giving the number of coins of each person
in the village, in counterclockwise order around the table. The total number of coins will fit inside an unsigned 64 bit integer.
The Output
For each input, output the minimum number of coins that must be transferred on a single line.
Sample Input
3
100
100
100
4
1
2
5
4
Sample Output
0
4
【题意】
【解析】
【代码】
/*********************************
* 日期:2013-11-22
* 作者:SJF0115
* 题号: 题目11300 - Spreading the Wealth
* 来源:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=25&page=show_problem&problem=2275
* 结果:AC
* 来源:UVA
* 总结:
**********************************/
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
#define N 1000000 + 10
long long Money[N],C[N],total,M,FirstMoney,ans;
int main() {
int i,n;
while(scanf("%d",&n) != EOF){
total = 0;
//每人分得的金币
for(i = 0;i < n;i++){
scanf("%lld",&Money[i]);
//总金额
total+= Money[i];
}
//均摊后的金币
M = total / n;
C[0] = 0;
for(i = 1;i < n;i++){
C[i] = C[i-1] + Money[i-1] - M;
}
//排序
sort(C,C+n);
//取中位数
FirstMoney = C[n/2];
ans = 0;
//计算转移的金币总额
for(i = 0;i < n;i++){
ans += abs(FirstMoney - C[i]);
}
printf("%lld\n",ans);
}//while
return 0;
}
分享到:
相关推荐
Novel iterative equalization based on energy-spreading transform
The BER performance of the coherent time-spreading OCDMA network is analyzed by considering the MAI and beat noises as well as the other additive noises. The influence and solution for the beat noise ...
The performance of normalized throughput in wavelength division multiplexing (WDM) based coherent time-spreading optical code division multiple access (TS-OCDMA) system is studied. The upper bound and...
矩阵用matlab代码实现
direct sequence spread spectrum matlab program to achieve the spreading of original data
扩散激活 使用在pyspark和graphframe中创建的使用扩散激活的扩散模型。
Spreading the Wealth and the Growth Dilemma The Logic of Uncontrolled Growth How Much Consumption? Making Space for a New Set of Voices Solving the Growth Dilemma Notes 11 Putting Poverty in ...
In this paper we propose a Swarm-based Spreading Points algorithm (SSP) for improving the solutions for packing problems. The SSP repositions the initial set of points and evolves it to improve the ...
Advanced particle effects like global/local Turbulence & Attractors, Particle sticking- propagation-spreading & particle to particle collisions (ideal for ice/fire simulation), Tornadoes, Volumetric ...
A virus is spreading rapidly, and your task is to quarantine the infected area by installing walls. The world is modeled as a 2-D array of cells, where 0 represents uninfected cells, and 1 represents...
A virus is spreading rapidly, and your task is to quarantine the infected area by installing walls. The world is modeled as a 2-D array of cells, where 0 represents uninfected cells, and 1 represents ...
1-4 Describe the spread mechanism used in UMTS, and please draw the power spectrum before and after spreading. 1-5 Please describe the functionalities of rake receiver? 2-1 Explain (draw) the 4 TCP-IP...
对于论文Phase transitions in information spreading on structured populations的翻译
Ultra Wide Band (UWB) is a technology for the transmission of data using techniques which cause a spreading of the radio energy over a very wide frequency band, with a very low power spectral density....
The OS SIS ICD Draft 1 provides an overview of the Galileo system, the signal-in-space radio frequency characteristics, the characteristics of the spreading codes, the message structures and the ...
Cortical spreading depression (CSD), which is a significant pathological phenomenon that correlates with migraines and cerebral ischemia, has been characterized by a wave of depolarization among ...
《黑暗即蔓延》是Flood-it类型游戏的翻版。 这是一个用PHP编写的开源免费游戏。 它应该托管在能够处理PHP的服务器上,并且很容易添加级别。
均匀与非均匀网络上的疾病传播动力学建模,胡瑶,闵乐泉,本文提出了基于均匀网络和不均匀网络的SIRS模型. 在均匀网络上, 本文证明了如果基本复制数$R_0$的值小于1, 则模型的无病平衡点是局部�
The problem with these traditional marketing techniques is that they have become less effective at spreading the word as people get better at blocking out these interruptions. Ten years ago, buying a...
伊利诺伊大学香槟分校的一篇博士学位论文,详尽分析了并行捕获方法的原理,希望对初学伪码捕获的同学有帮助。