Share the gold coin

【 Problem description 】

Sitting on the round table n personal , Each person has a certain amount of gold coins , The total number of gold coins can be n to be divisible by . Everyone can give some gold coins to his neighbors , In the end, everyone's gold coins are equal . Your task is to find the minimum number of gold coins to be transferred .

【 Input format 】

The first line is an integer n(n>=3), following n Each row has a positive integer , Give the number of gold coins each person has in counter clockwise order .

【 Output format 】

Output the minimum number of gold coins to be transferred .

【 The sample input 】

4

1

2

5

4

【 Sample output 】

4

【 Sample explanation 】

Let four people number 1,2,3,4. The first 3 I'll give it to you 2 personal 2 Gold coin ( become 1,4,3,4), The first 2 The individual and the third 4 I'll give it to each of you 1 personal 1 Gold coin .

【 Data range 】

N<=<=100000, Total gold coins <=10^9


Answer key :

set up a[i] For the first time i The initial number of gold coins per person ,

set up p by a The average number of arrays ,

set up c[i] For the first time i From the first i-1 The number of gold coins a person gets , that :

After mathematical transformation of the above equations, we can get :

C[i] = c[n] - (a[i] +···+ a[n]) + (n - i + 1)p,

The answer is

Ans = |c[1]| +···+ |c[n]|,

So set

e[i] = - (a[i] +···+ a[n]) + (n - i + 1)p;,

because a An array with the p It is known that , therefore e[i] It is known that ,

So the answer

Ans = |e[1] - (-c[n])| +···+|e[n] - (-c[n])|,

The answer is on the number axis -c[n] Separate to e[1] ~ e[n] The sum of the distances ,

To minimize the answer , be -c[n] take e The median of the array is optimal , The final statistical answer .

 #include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
inline int Get()
{
int x = ;
char c = getchar();
while('' > c || c > '') c = getchar();
while('' <= c && c <= '')
{
x = (x << ) + (x << ) + c - '';
c = getchar();
}
return x;
}
int n;
long long cc;
long long sum;
long long ans;
long long c[];
long long a[];
int main()
{
n = Get();
for(int i = ; i <= n; ++i)
{
a[i] = Get();
sum += a[i];
}
sum /= n;
a[] = a[n];
for(int i = ; i <= n; ++i)
c[i] = c[i - ] + a[i - ] - sum;
sort(c + , c + + n);
cc = -c[(n >> ) + ];
for(int i = ; i <= n; ++i) ans += abs(c[i] + cc);
printf("%lld", ans);
fclose(stdin), fclose(stdout);
}

Share the gold coin bzoj 3293 More articles about

  1. 【BZOJ-3293&amp;1465&amp;1045】 Share the gold coin &amp; Candy delivery &#215;2 Median + fool around with

    3293: [Cqoi2011] Share the gold coin Time Limit: 10 Sec  Memory Limit: 128 MBSubmit: 854  Solved: 476[Submit][Status] ...

  2. 【BZOJ3293】 Share the gold coin ( greedy )

    [BZOJ3293] Share the gold coin ( greedy ) Topic BZOJ Luogu Answer key Same as the previous question . #include<cstdio> #include<cmath> #include<al ...

  3. BZOJ3293: [Cqoi2011] Share the gold coin ( mathematics )

    3293: [Cqoi2011] Share the gold coin Time Limit: 10 Sec  Memory Limit: 128 MBSubmit: 1596  Solved: 969[Submit][Status ...

  4. 【 greedy + Median 】【UVa 11300】 Share the gold coin

    ( Solving equation modeling + The median is the shortest cumulative displacement ) Share the gold coin (Spreading the Wealth, UVa 11300) At the round table n personal , Each person has a certain amount of gold coins , The total number of gold coins can be n to be divisible by . Everyone can give his neighbors a ...

  5. cogs 1430. [UVa 11300] Share the gold coin

    1430. [UVa 11300] Share the gold coin **   Input file :Wealth.in   The output file :Wealth.out    Simple comparison of time limits :1 s   Memory limit :256 MB [ Title Description ] At the round table ...

  6. Java Realize the goal of sharing gold coins in the Blue Bridge Cup

    Share the gold coin At the round table n personal , Each person has a certain amount of gold coins , The total number of gold coins can be n to be divisible by . Everyone can give some gold coins to his neighbors , In the end, everyone's gold coins are equal . Your task is to find the minimum number of gold coins to be transferred . such as ,n=4, And 4 personal ...

  7. java Achieve the fifth Blue Bridge Cup Pirates Gold

    Pirates divide gold coins Yes 5 A pirate , Meet for a sailing race . There was a sudden change in the weather during the match , They were washed away . Happen to happen , They all passed by an unknown desert island on their way , And everyone is confident , Feel like the first person to pass through the island . The first person on the beach found ...

  8. BZOJ.3293.[CQOI2011] Share the gold coin ( Ideas )

    3293 Double the experience 1045 First consider whether the link can be broken into a chain . Obviously , Because it's impossible for a gold coin to move across the ring . So we enumerate breakpoints \(k\), Express \(k\) and \(k+1\) There is no exchange of gold between them . Make \(d_i=a_i-aver ...

  9. Share the gold coin [CQOI 2011] [BZOJ 3293]

    Description Sitting on the round table n personal , Each person has a certain amount of gold coins , The total number of gold coins can be n to be divisible by . Everyone can give some gold coins to his neighbors , In the end, everyone's gold coins are equal . Your task is to find the minimum number of gold coins to be transferred . Inpu ...

Random recommendation

  1. instanceof keyword

    instanceof yes Java.php A binary operator of ( Operator ), and ==.>.< It's the same thing . Because it's made up of letters , So too. Java Reserved keywords for . Its function is to determine whether the object on the left is the real object of the class on the right ...

  2. grunt Use

    grunt Server side , grunt-cli client 1.grunt Plug in installation : package.json, Deposit grunt Plug in required { "name": "demo" ...

  3. use case

  4. 【 turn 】Ansys 13.0 flexlm not running Perfect solution

    http://jingyan.baidu.com/article/af9f5a2dd9843a43150a4550.html Actually measured ,12.1 In this way, the problem can also be solved .

  5. java object-oriented -- Class loader and Class object

    Class loader jvm and Type of relationship When calling java Command to run a java The program , Will start a java Virtual machine process . The same jvm All threads of . All variables are in the same process , All use the jvm Memory area of the process . jvm End of process ...

  6. JDK8 BigDecimal API- establish BigDecimal Source code analysis 2

    Second articles , take your time Adjust the number of significant decimal places according to the index // The last one was created by strings BigDecimal In the code , Some of the code is not given , Make up this time // This is a method to adjust the number of decimal places when there is a valid exponent when parsing a character array privat ...

  7. Simple ( basic ) The post-processing of landscape photography - Novice tutorial -ps Basic post processing of photos

    Preface Photoshop It's not everything , But the lack of Photoshop But it can't be ! Landscape photography is not a recording process , You can't just “ I got it ”, I think it should be a creative process , Especially in the process of post-processing , More creative ...

  8. android Basics ----&gt;XMl Data analysis

    There are two most commonly used formats for transmitting data over the network ,XML and JSON, Let's first learn how to parse XML Formatted data ,JSON See my blog for more details (android Basics ---->JSON Data analysis ). analysis XML Format ...

  9. CKfinder for java Detailed explanation 2 : Thumbnail and image upload zoom

    We find <thumbs><enabled>true</enabled><url>�SE_URL%_thumbs/</url><dir ...

  10. silverlight A feasible solution for local serial port call And silverlight End code

    Follow up on the article above . stay javascript Exposure operation activex After receiving the serial port , Namely silverlight The display of serial port data is carried out at the terminal , Our display is relatively simple , Just to demonstrate , We do it every 1 Second for data acquisition and display , by ...