首页 > 试题广场 >

分玩具

[编程题]分玩具
  • 热度指数：2431 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
幼儿园里有有M个小朋友在课件玩耍，每个人手中现有ni个玩具。为了公平起见，老师需要让每个小朋友手中有相同数量的玩具。假设老师每次只能从一个人手中拿走两个玩具并给另一个小朋友。求老师最少需要做多少次这样的玩具转移。如果不存在可行的方案则输出-1。

输入描述:
每个输入包含一个测试用例。每个测试用例的第一行包含一个整数M（1 <= M<= 100），接下来的一行包含M个整数ni（1 <= ni <= 100）。


输出描述:
输出一行表示最少需要移动多少次可以平分苹果，如果方案不存在则输出-1。
示例1

输入

4
7 15 9 5

输出

3
示例2

输入

2
3 6

输出

-1
算法知识视频讲解
添加回答
Java
lmz9509头像 lmz9509 
/*
思路：这里有两种情况是不能实现评平均分配的
①总和不能被m整除
②总和可以被m整除，但是有某些组员距离平均值的差值不是偶数

当排除上面的情况之后，统计每个元素与平均值之间的差值的一半
最后把这个总和除以2，就是需要移动的次数，因为移动式成对的，一个数减少，就是添加到另一个数上面
*/
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader; 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int m = Integer.parseInt(br.readLine());
        String[] str = br.readLine().split(" ");
        int[] arr = new int[m];
        int sum = 0,avg = 0,count = 0;
        for(int i = 0;i<m;i++){
            arr[i] = Integer.parseInt(str[i]);
            sum += arr[i];
        }
        if(sum %m != 0){
            System.out.println(-1);
            return;
        }
        else{
            avg = sum / m;
            for(int i = 0;i<m;i++){
                int temp = Math.abs(arr[i] - avg);
                if(temp %2 != 0){
                    System.out.println(-1);
                    return;
                }else{
                    count += temp/2;
                }
            }
        }
        System.out.println(count/2);
    }
}

发表于 2020-05-20 20:17:05 回复(0)
Java
LHC0512头像 LHC0512
Java解法 
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] record = new int[n];
        int sum =0;
        for (int i = 0; i < n; i++) {
            record[i]=scanner.nextInt();
            sum+=record[i];
        }
        if (sum%n!=0){
            System.out.println(-1);
            return;
        }
        int average= sum/n;
        int count=0;
        for (int i = 0; i < n; i++) {
            int diff=record[i]-average;
            if (diff%2!=0){
                System.out.println(-1);
                return;
            }
            if (diff>0){
                count+=diff/2;
            }
        }
        System.out.println(count);
    }
}


发表于 2020-02-29 21:23:33 回复(0)
提交观点

问题信息

贪心 模拟 算法工程师 数据挖掘工程师 2019 数学 搜狐畅游
上传者：小小
难度：
3条回答 5963浏览

热门推荐

通过挑战的用户

查看代码

相关试题

分玩具

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号