Java实现蓝桥杯分金币

分金币

圆桌旁坐着n个人，每人有一定数量的金币，金币总数能被n整除。每个人可以给他左右相邻的人一些金币，

最终使得每个人的金币数目相等。你的任务是求出被转手的金币数量的最小值。

比如，n=4，且4个人的金币数量分别为1,2,5,4时，只需转移4枚金币（第3个人给第2个人两枚金币，

第2个人和第4个人分别给第1个人1枚金币）即可实现每人手中的金币数目相等。

[输入]

输入包含多组数据。每组数据第一行为整数n（n≤1 000 000），以下n行每行为一个整数，按逆时针顺序给出每个人拥有的金币数。输入结束标志为文件结束符（EOF）。

[输出]

对于每组数据，输出被转手金币数量的最小值。输入保证这个值在64位无符号整数范围内。

[样例输入]

3

100

100

100

4

1

2

5

4

[样例输出]

0

4

PS：

每一位的可能都是从前一位拿到一部分，然后给下一位一部分

move[i]=move[i-1]+num[i]-ave;

前一位拿到的加上自己的减去应该得到的，就是下一位的

那么现在是从头到尾的分金币，

每一位上都是我要移动的金币，

最短怎么算？

当然是给我要移动的金币排序，取中间值，把金币往中间值移动，

那么就是最短了，

有喜欢数学的可以百度看看大佬的数学推理

package 第六次模拟;

import java.util.Arrays;

import java.util.Scanner;

public class Demo6 {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		while(sc.hasNext()){

			int n = sc.nextInt();

			int num [] = new int [n];

			int sum =0;

			for (int i = 0; i < n; i++) {

				num[i]=sc.nextInt();

				sum+=num[i];

			}

			int ave = sum/n;

			int move [] = new int [n];

			for (int i = 1; i <n; i++) {

				move[i]=move[i-1]+num[i]-ave;

			}

			Arrays.sort(move);

			int result=0;

			int mid =move[n/2];

			for (int i = 0; i < move.length; i++) {

				result+=Math.abs(mid-move[i]);

			}

			System.out.println(result);

		}

	}

}

巴特西

Java实现蓝桥杯分金币

分金币

最新文章

热门文章