首页 > 试题广场 >

分玩具

[编程题]分玩具
  • 热度指数：2397 时间限制：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
算法知识视频讲解
添加回答
小蝌蚪666头像 小蝌蚪666 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void){
    int M, ni, sum = 0, average, count = 0;
    vector<int> toy;
    cin>>M;
    for(int i = 0; i < M; ++i){
        cin>>ni;
        sum += ni;
        toy.push_back(ni);
    }
    average = sum / M;
    if(sum % M){
        cout<<-1<<endl;
        return 0;
    }
    for(int ni : toy){
        if((ni-average)%2){
            cout<<-1<<endl;
            return 0;
        }
        if((ni-average) > 0){
            count += (ni-average)/2;
        }
    }
    cout<<count<<endl;
    return 0;
}
1. 首先判断玩具总数sum能否被M整除，不能整除输出-1返回
2.计算出平均值average，如果能平均分，这是最后每个小朋友分到的数量，在此基础上，遍历每个小朋友的数量ni，ni减去average为diff
3.diff必须为偶数，diff大于0表示这个小朋友要分给其他小朋友i次2个玩具，diff小于0，表示这个小朋友要从别的小朋友那里拿到j次2个玩具，diff必须为偶数，因为每次分配拿或者给的数量是2，一个数加减2的奇偶性不变，无论怎么分配diff奇偶性不变， 最后的结果是每个小朋友的diff为0，而0是偶数，所以一旦发现某个小朋友的diff为奇数，直接输出-1返回
4.diff为偶负数的小朋友要从diff为偶正数的小朋友那里拿玩具，最小次数就是依次让每个diff为负数的小朋友diff变为0，总的次数就是所有正偶数相加除以2或者负偶数相加除以-2
编辑于 2019-08-27 17:04:28 回复(0)
无心2019头像 无心2019 
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int m,sum=0;
    cin>>m;
    vector<int>num(m);
    for(int i=0;i<m;i++)
    {
        cin>>num[i];
        sum+=num[i];
    }
    if(sum%m!=0)
    {
        cout<<-1<<endl;
        return 0;
    }
    sort(num.begin(),num.end());
    int n=sum/m,i=0,j=m-1,res=0;
    while(i<j)
    {
        if(num[i]<=n-2&&num[j]>=n+2)
        {
            num[i]+=2;
            num[j]-=2;
            res++;
        }
        else if(num[i]==n&&num[j]>=n+2)
            i++;
        else if(num[j]==n&&num[i]<=n-2)
            j--;
        else if(num[i]==n&&num[j]==n)
        {
            i++;
            j--;
        }
        else 
        {
            cout<<-1<<endl;
        }
    }
    if(num[i]==n&&num[j]==n)
        cout<<res<<endl;
    else
        cout<<-1<<endl;
    return 0;
}

发表于 2019-08-20 21:07:33 回复(0)
pein531头像 pein531
对每个小朋友的玩具数量进行排序后利用双指针贪心求解 
n = int(input())
arr = sorted(list(map(int, input().split())))
total = sum(arr)
if total % n != 0:
    # 玩具总数不是n的倍数，无法完成均分玩具
    print(-1)
else:
    target = total // n
    # 两端双指针，右指针往左指针搬运
    left, right = 0, n - 1
    count = 0
    while left < right:
        while arr[left] != target and arr[right] != target:
            arr[left] += 2
            arr[right] -= 2
            count += 1
            if arr[left] > target&nbs***bsp;arr[right] < target:
                break
        if arr[left] == target and arr[right] == target:
            # 同时达到目标值，左右指针同时移动
            left += 1
            right -= 1
        elif arr[left] == target:
            # 左指针达到目标值，左指针移动
            left += 1
        elif arr[right] == target:
            # 右指针达到目标值，右指针移动
            right -= 1
        else:
            # 达不到目标值，无法完成任务
            count = -1
            break
    print(count)


发表于 2021-03-17 09:46:28 回复(0)
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)
包子山头像 包子山 
// 玩具变苹果 怎么都不可能吧 所以此题必输出-1 ；
#include <iostream>
using namespace std;
int main()
{
    int m;
    cin >> m;
    int res = 0;
    int counts = 0;
    int *data = new int[m];
    cin >> data[0];
    int sum = data[0];
    for(int i = 1;i<m;i++)
    {
        cin >> data[i];
        if(data[i]%2!=data[i-1]%2)
        {
            res = 1;
            break;
        }
        sum += data[i];
    }
    if(sum%m!=0)
        res = 1;
    if(res)
        cout << -1 << endl;
    else
    {
        int avr = sum/m;
        for(int i = 0;i<m;i++)
        {
            if(data[i]>avr)
                counts += (data[i]-avr)/2;
        }
        cout << counts << endl;
    }
    return 0;
}

发表于 2019-11-02 11:48:49 回复(0)
dragonlogin头像 dragonlogin 
#include<bits/stdc++.h>
using namespace std;

int main() {
	int n;
	while (cin >> n) {
		vector<int> f(n);
		int sum = 0;
		for (int i=0; i<n; ++i) {
            cin >> f[i];
			sum += f[i];
		}
		if (sum % n != 0) {
			cout << "-1" << endl;
			continue;
		}
		int avg = sum / n;
		int small = 0;
		for (int k : f) {
			if (k < avg ) {
				if (((avg-k) % 2) != 0) {
					cout << "-1" << endl;
					continue;
				} else {
					small += ((avg-k) >> 1);
				}
		
			}
		}
		cout << small << endl;

	}
	return 0;
}

发表于 2019-10-21 21:47:22 回复(0)
C/C++
nbgao头像 nbgao 
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin>>n;
    int a[n],s=0;
    for(int i=0;i<n;i++){
        cin>>a[i];
        s += a[i];
    }
    int t = s/n, d=0;
    if(s != n*t)
        cout<<-1<<endl;
    else{
        s = 0;
        for(int i=0;i<n;i++){
            d = abs(a[i]-t);
            if(d&1){
                cout<<-1<<endl;
                break;
            }else
                s += d;
        }
        cout<<s/4<<endl;
    }
    return 0;
}

发表于 2019-10-20 01:19:54 回复(0)
EnvyEvil头像 EnvyEvil 
# 思路
# 找到list中比平均值小的那部分，与平均作差并累加
# 因为一次操作 = 高于平均的某个数 - 1 and 低于平均的某个数 + 1
# 故仅计算低于平均值的部分与平均值的差即可
M = int(input())
ni = list(map(int, input().split()))
sum_n = sum(ni)  # ni 中苹果的总数
avg_n = sum_n // M  # ni 中苹果的平均数
ni.sort()  # 使 ni 有序，便于之后只选择小于平均数的部分计算需要的移动次数

if sum_n % M is not 0:  # 总的苹果数若不能被平分 则不存在可以平分的方法
    print(-1)
else:
    res = 0
    i = 0
    while ni[i] < avg_n:  # 取比平均苹果数量小的部分，累加计算与平均值的差
        res += avg_n - ni[i]
        i += 1
    # 上面是按照移动一个苹果来计算的 因为一次只能拿两个苹果 故如果结果不能被2整除 则不存在可以平分的方法
    # 最后结果 res 也需要除以2
    print(res // 2) if res % 2 == 0 else print(-1)
运行时间 24ms
占用内存 3429k
编辑于 2019-09-20 15:24:30 回复(0)
cy助我头像 cy助我 
"运行时间：34ms"
"占用内存：3432k"
m = int(input())
li = list(map(int,input().split()))
avg = sum(li) // m                 # 平均每人分多少个
flag = sum(li) % m                 # 是否能平分（没有余数就能平分)
res = 0
if flag == 0:
    for i in li:
        if abs(i-avg)%2 == 1:       # 如果奇数个，由于每次只能拿2个，故无法分匀
            print(-1)
            break
        else:                 # 如果偶数个，差多少（多的话退）补多少
            res += abs(i-avg) // 2  # 退的 和 补的 相加，最后res取1/2，则为移动次数
    print(res // 2)
else:
    print(-1)

编辑于 2019-07-26 21:09:00 回复(0)
Python
handsomefellow头像 handsomefellow
def devide_candy(messages):
    N = int(messages[0].strip())
    ori = []
    for i in range(N):
        ori.append(int(messages[1].strip().split()[i]))

    if sum(ori)%len(ori)!=0:
        print(-1)
        return 0
    avg = sum(ori)//len(ori)
    for i in ori:
        if abs(i-avg)%2!=0:
            print(-1)
            return 0
    res =[]
    for j in ori:
        a = j-avg
        if a>0:
            res.append(a)
    print(sum(res)//2)
    return 0
if __name__ == '__main__':
    import sys
    messages = sys.stdin.readlines()
    devide_candy(messages)
发表于 2020-05-20 10:55:44 回复(0)
小云云是真的很想学习头像 小云云是真的很想学习 
M = int(input())
N = list(map(int, input().split()))
N.sort()
res = 0
if sum(N) % M == 0:
    avg = sum(N) // M
    N = [abs(i - avg) for i in N]
    res = sum(N) // 4
else:
    res = -1
print(res)

发表于 2019-11-20 13:28:58 回复(0)
hzdms头像 hzdms 
n = int(input())
nums = list(map(int, input().split()))

total = sum(nums)
if not total % n == 0:
    print(-1)
    exit()
aver = total // n
pos = 0
for num in nums:
    diff = num - aver
    if diff % 2 == 1:
        print(-1)
        exit()
    if diff > 0:
        pos += diff // 2
print(pos)
    


发表于 2019-09-02 16:50:26 回复(0)
山阴路的两棵树头像 山阴路的两棵树 
import java.util.Scanner;

public class Main{
    public static void main(String [] argvs){
        // input
        Scanner sc = new Scanner(System.in);
        int count = Integer.valueOf(sc.nextLine());
        int [] apples = new int[count];
        String [] applestr = sc.nextLine().split(" ");
        int total = 0;
        for(int i=0;i<applestr.length;i++){
            apples[i] = Integer.valueOf(applestr[i]);
            total+=apples[i];
        }
        sc.close();
        
        // 不能均分
        if(total%count!=0){
            System.out.println("-1");
            return;
        }
        
        int appleTarget = total/count;
        int mod = appleTarget%2;
        int result = 0;
        // 1.DP解法. 2.奇偶性解法
        // 奇偶性：因为一次只能拿两个，所以本身拥有的apple数要和目标数同奇偶。转移次数=差值/2，有因为同时计算了拿出和放入，故最后result除2
        for(int i=0;i<apples.length;i++){
            int currApple = apples[i];
            if(currApple%2!=mod){
                System.out.println("-1");
                return;
            }
            int diff = currApple-appleTarget;
            diff = diff>0? diff:(-diff);
            result += diff/2;
        }
        System.out.println(result/2);
    }
}

发表于 2019-08-26 07:43:06 回复(0)
solanina头像 solanina
#include<iostream>
using namespace std;

int main(){
    //输入数据处理
    int M;
    cin>>M;
    int n[M];
    for(int i=0;i<M;++i)
    {
        cin>>n[i];
    }
    //获得和数进行下一步判断
    int sum=0;
    for(int i=0;i<M;++i)
    {
        sum+=n[i];
    }
    //如果不能平分 返回-1
    if(sum%M!=0) cout<<-1<<endl;
    //如果能评分 计算平均数 多退少补原则 计算总共需要补多少个苹果 再/2获得结果
    else
    {
    sum/=M;
    int res=0;
    for(int j=0;j<M;++j)
    {
        if(n[j]<sum) res+=sum-n[j];
    }
    cout<<res/2<<endl;
    }
    
    
    
    return 0;
}
发表于 2019-08-21 16:10:58 回复(0)
C/C++
Hertz啊丶头像 Hertz啊丶
改的一楼大哥的python代码，思路一毛一样 
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
    int n;cin>>n;
    int sum=0;
    int avg;
    int flag;
    int res=0;
    vector<int>vec(n,0);
    for(int i=0;i<n;i++){
        cin>>vec[i];
        sum+=vec[i];
        }
    avg=sum/n;
    flag=sum%n;
    if(flag==0){
        for(int i=0;i<n;i++){
            if((vec[i]-avg)%2==1){cout<<-1<<endl;
                                 break;}
            else res+=abs(vec[i]-avg)/2;
        }cout<<res/2<<endl;
    } else cout<<-1<<endl;
}



发表于 2019-08-15 15:45:23 回复(0)
牛客372964232号头像 牛客372964232号
C++ 
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
    int n; cin >> n;
    vector<int> vec(n,0);
    for(int i = 0; i < n;i++) cin >> vec[i];
    sort(vec.begin(), vec.end());
    int num = 0;
    while(vec[n-1] > vec[0])
    {
        if(vec[n-1] == vec[0]) break;
        if(vec[n-1] - vec[0] <= 3) 
        {
            cout << -1 << endl;
            return 0;
        }
        vec[0] +=  2;
        vec[n-1] -=  2;
        num++;
        sort(vec.begin(), vec.end());
    }
    cout << num << endl;
    return 0;
}

发表于 2019-08-06 16:21:38 回复(0)
C/C++
王志程头像 王志程
//猜测：只要能分，方法数应该是一样的？（如果不来回瞎传）
//所有数求和算平均，平均值不为整数，输出-1
//之后算每个数和平均值的差值，差值除以4为整数，即为结果；否则为-1
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    while(cin>>n)
    {
        vector<int>a(n);
        int sum = 0;
        int diff = 0;
        for(int i=0;i<n;i++)
        {
            cin>>a[i]; sum+=a[i];
        }
        if(sum%n != 0 ) cout<<-1<<endl;
        else
        {
            int avg = sum/n;
            for(int i=0;i<n;i++)
                diff += abs(a[i]-avg);
            if(diff%4 == 0) cout<<diff/4<<endl;
            else cout<<-1<<endl;
        }
            
    }
}

发表于 2019-07-31 10:30:36 回复(0)
离开浪浪山头像 离开浪浪山
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int N;
    cin>>N; 
    int ans=0;
    int sum=0;
    int a[N];
    for(int i=0;i<N;i++)
    {
    cin>>a[i];
    sum+=a[i];
    }
    int middle=sum/N;
    if(sum%N)
    {
        cout<<"-1"<<endl;
    }
    else
    {
    for(int i=0;i<N;i++)
    {
        if(a[i]<middle)
        ans+=(middle-a[i])/2;
        else
        continue;
    }
    cout<<ans<<endl;
    }
    return 0;
}
发表于 2019-07-30 09:46:12 回复(0)
Python
lzher0头像 lzher0 
def dis_toy(m, n):
    if sum(n)%m != 0:
        return -1
    toy = sum(n)//m
    res = 0
    for s in n:
        if s < toy:
            more = toy-s
            if more%2 != 0:
                return -1
            res += more//2
    return res
m = int(input())
n = list(map(int,input().split()))
print(dis_toy(m,n))
编辑于 2019-07-10 10:27:20 回复(2)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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