[编程题]分苹果
- 热度指数：55507 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
n 只奶牛坐在一排，每个奶牛拥有 ai 个苹果，现在你要在它们之间转移苹果，使得最后所有奶牛拥有的苹果数都相同，每一次，你只能从一只奶牛身上拿走恰好两个苹果到另一个奶牛上，问最少需要移动多少次可以平分苹果，如果方案不存在输出 -1。
输入描述:
每个输入包含一个测试用例。每个测试用例的第一行包含一个整数 n（1 <= n <= 100），接下来的一行包含 n 个整数 ai（1 <= ai <= 100）。
输出描述:
输出一行表示最少需要移动多少次可以平分苹果，如果方案不存在则输出 -1。
示例1
输入
4 7 15 9 5
输出
3
import java.util.Arrays;
import java.util.Scanner;
public class Main{
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String line = scanner.nextLine();
int n = Integer.parseInt(line);
line = scanner.nextLine();
String []s = line.split(" ");
int []arr = new int[n];
for (int i = 0;i < n;i ++) {
arr[i] = Integer.parseInt(s[i]);
}
System.out.println(step(arr));
}
public static int step(int []arr) {
int n = arr.length;
int sum = 0;
//统计和，计算平均值
for (int i = 0;i < n;i ++) {
sum += arr[i];
}
int ave = sum/n;
//如果不能整除，说明无法分配
if (ave * n != sum) {
return -1;
}
//如果和平均值的差值不为偶数，那么就失败
for (int i = 0;i < n;i ++) {
if ((arr[i] - ave) % 2 != 0) {
return -1;
}
}
//排序数组，以便从大到小统计
Arrays.sort(arr);
int rem = 0;
//统计溢出的值
for (int i = n - 1;i >= 0;i --) {
if (arr[i] - ave >= 2) {
rem += arr[i] - ave;
arr[i] = ave;
}
}
//将溢出值按需分配。从最小的开始分，如果最小的都满足不了，那就gg
int count = 0;//统计次数
for (int i = 0;i < n;i ++) {
int val = arr[i];
while (val < ave && rem > 0) {
count ++;
rem -= 2;
val += 2;
}
if (val != ave) {
return -1;
}
}
return count;
}
}
发表于 2018-05-19 12:01:07
回复(0)
更多回答
#include <iostream> #include <stdio.h> using namespace std; /* 想通了就挺简单的，，如果苹果总数不能整除人数，证明无论怎么分，总会有人多出一些 苹果。 如果能整除，那么每个人的最终的苹果数目一定是平均数，不然不可能相等。所以 只需要把低于平均数那一部分补上，把高于平均数那一部分减掉就可以了。当然如果， 补 上的那一部分不能整除2，证明这个人是不能通过2个苹果的转移来达到平均数，即无论怎么 分，也不可能每个人的苹果都一样。 如数据： 3 2 3 1 6 1 4 1 */ int n,a[105]; int main(){ int cnt,flag,sum=0; int averApple = 0; cin>>n; for(int i=0;i<n;i++){ cin>>a[i]; sum+=a[i]; } if( 0 != (sum % n)){ cout<<-1<<endl; return 0; } averApple = sum/n; cnt = 0; for(int i = 0; i<n ; i++){ //不能用2去补齐，使该数等于平均数，即分到最后每一个人的苹果不可能相等 if(1== (( averApple - a[i])&0x01)){ cout<<-1<<endl; return 0; } if(averApple>=a[i]){ cnt = cnt + ( averApple - a[i])/2; } } cout<<cnt<<endl; return 0; }
编辑于 2016-08-27 23:32:18
回复(8)
这题感觉更像一道数学题
import java.util.*;
public class Main{
public static int avg(int[] num){
int average=0;
int sum=0;
int len=num.length;
for(int i=0;i<len;i++){
sum+=num[i];
}
average=sum/len;
if(sum%len!=0){
return -1;
}
for(int i=0;i<len;i++){
int t=Math.abs((num[i]-average));
if(t%2!=0)
return -1;
}
int index=0;
for(int i=0;i<len;i++){
if(num[i]>average)
index+=(Math.abs(num[i]-average)/2);
}
return index;
}
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
while(scanner.hasNextInt()){
int n=scanner.nextInt();
int[] num=new int[n];
for(int i=0;i<n;i++){
num[i]=scanner.nextInt();
}
System.out.println(avg(num));
}
}
}
发表于 2016-08-07 21:34:54
回复(3)
//这个题目其实非常简单，只要考虑两个条件，第一，总数一定能被牛的数量整除，第二，每头牛
//比平均值多出来的苹果数一定能被2整除，不满足这两个条件的输出-1，满足的情况下，将比平均值
//多出的苹果数除2，就是移动次数
import java.util.Arrays;
import java.util.Scanner;
/**
* Created by 梅晨 on 2017/9/13.
*/
public class Main {
public static void main(String[] args){
Scanner in = new Scanner(System.in);
while (in.hasNext()){
int num = in.nextInt();
int[] apples = new int[num];
int sum = 0;
for(int i = 0; i < num; i++){
int a = in.nextInt();
sum += a;
apples[i] = a;
}
int avg = sum / num;
if(sum % num != 0){
System.out.println(-1);
return;
}
int res = 0;
for(int n : apples){
if(n > avg){
int over = n - avg;
if(over % 2 != 0){
System.out.print(-1);
return;
}else {
res += over / 2;
}
}
}
System.out.println(res);
}
}
}
发表于 2017-09-13 00:47:29
回复(5)
#include<iostream>
#include<vector>
using namespace std;
int main(){
int n;
while (cin >> n){
vector<int>num(n);
int sum = 0;
for (vector<int>::iterator iter = num.begin(); iter != num.end(); iter++){
cin>>*iter;
sum = sum + *iter;
}
if (sum%n != 0){
cout << '-1' << endl;
return 0;
}
sum = sum / n;
int count = 0;
for (vector<int>::iterator iter = num.begin(); iter != num.end(); iter++){
int temp = *iter - sum;
if (temp % 2 != 0){
cout << '-1' << endl;
return 0;
}
if (temp > 0){
count=count+temp/2;
}
}
cout << count << endl;
}
return 0;
}
发表于 2016-08-26 21:45:32
回复(2)
#-*- coding: utf8 -*-
def avgNum(a,n):
avg=sum(a)/n
i=j=0
count=0
while i<n and j<n:
while i<n and a[i]>=avg:i+=1
if i<n and (avg-a[i])%2!=0:
return -1
while j<n and a[j]<=avg:j+=1
if j<n and (a[j]-avg)%2!=0:
return -1
if (i<n and j<n):
a[j]-=2
a[i]+=2
count+=1
if (j<n and a[j]!=avg) or (i<n and a[i]!=avg):
return -1
return count
n=input()
a=map(int,raw_input().strip().split(' '))
print avgNum(a,n)
发表于 2018-07-31 14:51:35
回复(0)
#include <stdio.h>
#include <vector>
#include <algorithm>
/*
题目描述
n 只奶牛坐在一排，每个奶牛拥有 ai 个苹果，现在你要在它们之间转移苹果，
使得最后所有奶牛拥有的苹果数都相同，每一次，你只能从一只奶牛身上拿走恰好两个苹果到另一个奶牛上，
问最少需要移动多少次可以平分苹果，如果方案不存在输出 -1。
思路：
1.先遍历数组，统计每个奶牛手中的苹果
2.求平均数m，若可以整除，表示右分配方案，否则没有。
3.遍历每个元素，比较当前元素与m得到差值，如果差值不是2的倍数，说明无论如何不存在移动方案使得
条件成立。如果差值是2的倍数，就往后找大于平均值的元素作为填补。
*/
using namespace std;
int main()
{
int n;
scanf("%d", &n);
vector<int> cow(n, 0);
int sum = 0;
for (int i = 0; i < n; i++)
{
scanf("%d", &cow[i]);
sum += cow[i];
}
if (sum %n != 0)
{
printf("%d\n",-1);
return 0;
}
int average = sum / n;
int step = 0;
for (int i = 0; i < n; i++)
{
int gap = cow[i] - average;
if (gap == 0)
continue;
if(gap %2 != 0)
{
printf("%d\n",-1);
return 0;
}
for (int j = 0; j < n; j++)
{
if (i == j)
continue;
while (gap < 0 && cow[j] > average)
{
step++;
cow[i] += 2;
cow[j] -= 2;
gap = cow[i] - average;
}
}
}
printf("%d\n", step);
return 0;
}
发表于 2018-07-29 23:43:03
回复(0)
/***
* 首先说明两种不能平分的情况
* 第一：苹果总数不能整除牛的数量
* 第二：牛拥有的苹果数与苹果的平均数相差奇数
*
* 如果不属于以上两种情况，可以将苹果数多于平均数的牛的苹果分出去，计算分的次数就可以了。
*/
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
int[] array = new int[num];
for(int i=0;i<num;i++){
array[i] = sc.nextInt();
}
System.out.println(getCount(array));
}
public static int getCount(int[] array){
int count = 0;
int total = 0;
for(int i=0;i<array.length;i++){
total += array[i];
}
//情况一
if(total%(array.length) != 0){
return -1;
}
int avg = total / array.length;
for(int i=0;i<array.length;i++){
//情况二
if((array[i] - avg)%2 != 0){
return -1;
}else{
//分发的次数
if(array[i] - avg > 0){
count = count + (array[i] - avg)/2;
}
}
}
return count;
}
}
* 首先说明两种不能平分的情况
* 第一：苹果总数不能整除牛的数量
* 第二：牛拥有的苹果数与苹果的平均数相差奇数
*
* 如果不属于以上两种情况，可以将苹果数多于平均数的牛的苹果分出去，计算分的次数就可以了。
*/
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
int[] array = new int[num];
for(int i=0;i<num;i++){
array[i] = sc.nextInt();
}
System.out.println(getCount(array));
}
public static int getCount(int[] array){
int count = 0;
int total = 0;
for(int i=0;i<array.length;i++){
total += array[i];
}
//情况一
if(total%(array.length) != 0){
return -1;
}
int avg = total / array.length;
for(int i=0;i<array.length;i++){
//情况二
if((array[i] - avg)%2 != 0){
return -1;
}else{
//分发的次数
if(array[i] - avg > 0){
count = count + (array[i] - avg)/2;
}
}
}
return count;
}
}
发表于 2018-05-19 13:35:49
回复(0)
// 思路挺简单的，因为只能移动2个，因此每个奶牛拥有的苹果减去平均值，
//如果不是2的倍数，就不可能使得最后相等的苹果数.
//算移动的次数可以只算小于平均值（或大于）的移动次数。
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
int n = sc.nextInt();
int[] appleNum = new int[n];
int sum = 0;
for(int i=0;i<n;i++){
appleNum[i] = sc.nextInt();
sum += appleNum[i];
}
if(sum%n==0){
int avg = sum/n;
int step = 0;
boolean flag = false;
for(int i=0;i<n;i++){
if(appleNum[i]>avg){
if((appleNum[i]-avg)%2!=0){
flag = true;
break;
}
}else if(appleNum[i]<avg){
if((avg-appleNum[i])%2==0){
step += (avg-appleNum[i])/2;
}else{
flag = true;
break;
}
}else{
continue;
}
}
if(flag){
System.out.println(-1);
}else{
System.out.println(step);
}
}else{
System.out.println(-1);
}
}
}
}
发表于 2017-08-18 17:16:27
回复(0)
#include <iostream>
using namespace std;
int main()
{ int n,a[109],sum=0,avg=0,count=0; bool flag = true; cin>>n; for(int i=0;i<n;i++) { cin>>a[i]; sum += a[i]; } if(sum%n != 0) flag = false; else{ avg = sum/n; for(int i=0;i<n;i++) if(a[i]>avg) { if((a[i]-avg)%2 != 0) { flag = false; break; }else count += (a[i]-avg)/2; } } if(flag) cout<<count<<endl; else cout<<-1<<endl; return 0;
}
发表于 2018-01-13 00:45:37
回复(0)
思路很简单，先按条件过滤：(1) 总数不能平分为n份返回false；(2) 有奶牛所拥有的苹果数和总体平均数奇偶性不同返回false。
排序+双指针
- 对数组进行排序；
- 准备一个指针L，指向第一个小于平均数的数；准备一个指针R，指向第一个大于平均数的数；
- 如果第R头奶牛把超出平均数的苹果分给第L头奶牛可以使得两头奶牛的苹果都调整为平均数，进行分配，L往左动，R往右动；如果分过去后第L头奶牛的苹果还是不够，进行分配，L不动，R往右动；如果分过去后会超，则按第L头奶牛的需求分配，L往左动，R不动。
这样双指针走过的区域一定是已经分配完毕的区域，双指针走完后检查一下第一头奶牛和最后一头奶牛拥有的苹果数是不是都为平均数就可以了。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
public class Main {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line;
while((line = br.readLine()) != null){
int n = Integer.parseInt(line);
String[] strs = br.readLine().split(" ");
int[] apples = new int[n];
System.out.println(solve(strs, apples, n));
}
}
private static int solve(String[] strs, int[] apples, int n){
int total = 0;
for(int i = 0; i < n; i++){
apples[i] = Integer.parseInt(strs[i]);
total += apples[i];
}
if(total % n != 0){
return -1; // 无法平分成n份
}else{
int goal = total / n;
for(int i = 0; i < n; i++){
if(((apples[i] + goal) & 1) != 0){
return -1; // 有一只奶牛的苹果数与目标苹果数奇偶性不同
}
}
Arrays.sort(apples);
int L = lowerBound(apples, goal);
int R = upperBound(apples, goal);
if(apples[L] == goal){
L--;
}
int times = 0;
while(L >= 0 && R < n){
int diff = apples[R] - goal;
if(apples[L] + diff == goal){
apples[L--] += diff;
apples[R++] -= diff;
times += diff >> 1;
}else if(apples[L] + diff < goal){
apples[L] += diff;
apples[R++] -= diff;
times += diff >> 1;
}else{
diff = goal - apples[L];
apples[R] -= diff;
apples[L--] += diff;
times += diff >> 1;
}
}
return apples[0] == goal && apples[n - 1] == goal? times: -1;
}
}
private static int lowerBound(int[] nums, int target) {
int left = 0, right = nums.length - 1, index = 0;
while(left < right){
int mid = left + ((right - left) >> 1);
if(nums[mid] > target){
right = mid - 1;
}else{
index = mid;
left = mid + 1;
}
}
return index;
}
private static int upperBound(int[] nums, int target) {
int left = 0, right = nums.length - 1, index = 0;
while(left < right){
int mid = left + ((right - left) >> 1);
if(nums[mid] <= target){
left = mid + 1;
}else{
right = mid;
}
}
return left;
}
} 数学
还有一种数学解法，先定义
和
两个变量。然后遍历数组，找到每个比平均数
多的苹果数
，累加上
，如果不是偶数，则无法完成分苹果；找到每个比平均数少的苹果数，累加上
，如果不是偶数，也无法完成分苹果。最后对比和是否相等，其实就是“劫富济贫”，看看最终财富能否平均分配。
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
String[] strs = br.readLine().split(" ");
int[] arr = new int[n];
int sum = 0;
for(int i = 0; i < n; i++){
arr[i] = Integer.parseInt(strs[i]);
sum += arr[i];
}
if(sum % n != 0 || n == 1){
System.out.println(n == 1? 0: -1);
}else{
int target = sum / n;
int less = 0, more = 0;
boolean flag = true;
for(int i = 0; i < n; i++){
if((Math.abs(target - arr[i]) & 1) != 0){
flag = false;
break;
}
if(arr[i] < target){
less += target - arr[i];
}else if(arr[i] > target){
more += arr[i] - target;
}
}
if(less != more){
flag = false;
}
System.out.println(flag? less >> 1: -1);
}
}
}
编辑于 2022-03-22 16:06:52
回复(0)
// 导包部分，考虑记忆问题，直接使用*代替一切
import java.io.*;
import java.lang.*;
import java.util.*;
public class Main{
public static void main(String[] args) throws IOException {
// 固定部分，读取输入
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(reader.readLine());
if( n < 1 || n > 100){
System.out.print(-1);
return;
}
String[] x = reader.readLine().split(" ");
if(x.length != n){
System.out.print(-1);
return;
}
/**
* 解题思路：
* 1、公式： 增加次数 = 减少次数， 所以只要求增加次数综合，或者减少次数总和
* 2、条件约束：
* 2.1 要么全部是双数，要么全部是单数
* 2.2 如何判断全部双数或者单数，根据第一个数字作为参考，后续每一个数字必须与第一个类型一致，使用标志位changeNum
* 2.3 总数 应该能够 被总个数整除，即 sum % n == 0
* 3、利用平均数计算每一个数需要移动的次数，根据公式，只需要计算增加次数 ，或者是减少次数即可
*/
int changeNum = 0;
int sum = 0;
for(int i=0; i<n; i++){
int value = Integer.parseInt(x[i]);
//双数
if( value%2 == 0){
if(changeNum == 0 || changeNum == 1){
//被第一个双数占用，后续元素不能出现单数
changeNum = 1;
}else {
System.out.print(-1);
return;
}
}else{
if(changeNum == 0 || changeNum == 2){
//被第一个双数占用，后续元素不能出现单数
changeNum = 2;
}else {
System.out.print(-1);
return;
}
}
sum = sum + Integer.parseInt(x[i]);
}
if(sum % n != 0){
System.out.print(-1);
return;
}
test(n, x, sum);
}
public static void test(int n, String[] x, int sum){
int moveNum = 0;
int avd = sum / n;
for(int i=0; i<n;i++){
int ivalue = Integer.parseInt(x[i]);
if(ivalue < avd){
moveNum = moveNum + (avd - ivalue)/2;
}
}
System.out.print(moveNum);
}
}
发表于 2020-09-23 11:59:48
回复(0)
#include<iostream>
(720)#include<vector>
using namespace std;
int main()
{
int n;
while(cin>>n)
{
int i=0;int sum=0;
vector<int>apples(n);
while(i<n)
{
cin>>apples[i];
sum+=apples[i];
i++;
}
if(sum%n) //没有平均数直接continue
{
cout<<-1<<endl;
continue;
}
i=0;
int p=sum/n;
int c=0;
for(;i<n;i++)
{
if(abs(apples[i]-p)%2) //不能以2分
{
break;
}
if(apples[i]<p)
{
c+=(p-apples[i])/2; //小的需要填的2
}
}
cout<<(i==n?c:-1)<<endl;
}
}数学题，把考虑的条件减少这样减少代码量
发表于 2020-05-07 10:21:00
回复(0)
import java.util.*;
public class Main {
/*
* n 只奶牛坐在一排，每个奶牛拥有 ai 个苹果，现在你要在它们之间转移苹果，使得最后所有奶牛拥有的苹果数都相同，
* 每一次，你只能从一只奶牛身上拿走恰好两个苹果到另一个奶牛上，问最少需要移动多少次可以平分苹果，如果方案不存在输出 -1。 输入描述:
* 每个输入包含一个测试用例。每个测试用例的第一行包含一个整数 n（1 <= n <= 100），接下来的一行包含 n 个整数 ai（1 <= ai <=
* 100）。
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner cin = new Scanner(System.in);
int n = cin.nextInt();// 拥有苹果的奶牛数量（奶牛都开始学会分享了 太可怕了）
int a[] = new int[n];
int sum = 0;//总苹果数
int out = 0;//移动次数
for (int i = 0; i < n; i++) {
a[i] = cin.nextInt();
sum = sum + a[i];//总苹果数
}
int temp = sum / n;
if (sum % n != 0) {
System.out.print(-1);
} else {
int x = 0;
for (int i = 0; i < n; i++) {
if (Math.abs(a[i] - temp) % 2 != 0) {
//System.out.print(-1);
x = 1;
break;
}
}
if (x == 0) {
for (int i = 0; i < n; i++) {
if (a[i] < temp) {
out = out + ((temp - a[i]) / 2);
// System.out.println(temp+" "+((temp-a[i])/2));
}
}
System.out.print(out);
} else {
System.out.print(-1);
}
}
}
}
发表于 2019-11-29 09:37:19
回复(0)
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
/**
*这个题目是求解最少的移动次数。细节上考虑，是要将一个奶牛身上的苹果转移到另一个奶牛身上，但是实际上求最小，并不需要一个一个的转移。
*奶牛拥有的少于平均多少个，除以二就是最少需要的次数。遍历所有的奶牛，计算少于平均的奶牛需要多少个就可以了，如果想省略判断是否少于平均，
*也是可以的，直接用奶牛拥有的苹果个数减去平均值，取绝对值除2就可以了，但是由于多的也计算，少的也计算，那么最后要将总的次数除以二。
*注意细节问题：
*一：如果总苹果sum( = a1 + a2 + .. + an）不能整除奶牛个数n,则无法平均，无解
*二：每次只能从一个奶牛上恰好拿2个到另一个奶牛，这个和数字运算有关，奇数和偶数减2仍然保持自身奇偶性，
*但是平均数只可能是奇数或者偶数中的一种，所以输入的每个数必须和平均数保持一致奇偶性，否则无解。
*/
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
boolean haveOdd = false;
boolean haveEven = false;
int sum = 0;
int avg = 0;
int numNo = Integer.parseInt(br.readLine().trim());
int[] arrNum = new int[numNo];
String[] arrInput = br.readLine().trim().split(" ");
int step = 0;
for (int i=0; i<numNo; i++) {
arrNum[i] = Integer.parseInt(arrInput[i]);
sum += arrNum[i];
if (arrNum[i] % 2 == 0) {
haveEven = true;
} else {
haveOdd = true;
}
}
if (sum % numNo != 0) {//不能整除
System.out.println(-1);
return;
}
avg = sum /numNo;
if (((avg % 2 == 0) && haveOdd == true) || ((avg % 2 == 1) && haveEven == true)) {//判断每个数和avg的奇偶性是否一致
System.out.println(-1);
return;
}
for (int i=0; i<numNo; i++) {//核心运算
if (arrNum[i] < avg) {
step += (avg - arrNum[i]) >> 1;//除以2
}
}
System.out.println(step);
}
}
编辑于 2018-11-02 15:38:28
回复(0)
public class Main{ public static void main(String[] args) { Scanner scanner=new Scanner(System.in); int num=scanner.nextInt(); int a[]=new int[num]; int count=0; for (int i=0;i<num;i++){ a[i]=scanner.nextInt(); count+=a[i]; } if (count%num!=0) System.out.println(-1); else { int countofone=count/num; int times=0; int i; for (i=0;i<num;i++){ if ((a[i]-countofone)>0&&(a[i]-countofone)%2==0){ times+=(a[i]-countofone)/2; } if ((a[i]-countofone)>0&&(a[i]-countofone)%2!=0) break; } if (i==num) System.out.println(times); else System.out.println(-1); } } }
发表于 2018-09-12 20:38:16
回复(0)
//初学者，哪里有问题请多指教，谢谢。
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner s = new Scanner(System.in);
int n = s.nextInt();
int[] ai = new int[n];
int sum = 0,avg = 0,num = 0;
for(int i = 0 ; i < n ; i++){
ai[i] = s.nextInt();
sum += ai[i];
}
//若是苹果总和不能平均分配给n个奶牛，返回。否则返回最后的平均数
if( (sum % n) != 0){
System.out.println(-1);
return;
}
else{
avg = sum/n;
}
//每个奶牛的苹果数和平均数的绝对差值是否为2的倍数，判断数值能否达到平均数，能则计算所有数的倍数和。
//倍数和等于转移苹果次数的两倍（一加一减）。
for(int i = 0 ; i < n ; i++){
if((Math.abs(ai[i] - avg) % 2) != 0){
System.out.println(-1);
return;
}
num += Math.abs(ai[i] - avg)/2;
}
System.out.println(num/2);
}
}
public class Main{
public static void main(String args[]){
Scanner s = new Scanner(System.in);
int n = s.nextInt();
int[] ai = new int[n];
int sum = 0,avg = 0,num = 0;
for(int i = 0 ; i < n ; i++){
ai[i] = s.nextInt();
sum += ai[i];
}
//若是苹果总和不能平均分配给n个奶牛，返回。否则返回最后的平均数
if( (sum % n) != 0){
System.out.println(-1);
return;
}
else{
avg = sum/n;
}
//每个奶牛的苹果数和平均数的绝对差值是否为2的倍数，判断数值能否达到平均数，能则计算所有数的倍数和。
//倍数和等于转移苹果次数的两倍（一加一减）。
for(int i = 0 ; i < n ; i++){
if((Math.abs(ai[i] - avg) % 2) != 0){
System.out.println(-1);
return;
}
num += Math.abs(ai[i] - avg)/2;
}
System.out.println(num/2);
}
}
发表于 2018-09-09 14:50:11
回复(0)
思路：每次都把最多苹果的奶牛拿两个给最少的（差值大于2个，3个起），反复循环并记录下次数
关键点在于：while(a[ma]-a[mi]>2) 这个循环，如果不能平分，最后，最多苹果的奶牛和最少苹果的奶牛差值为1，如果平分，则最多苹果的奶牛和最少苹果的奶牛差值为0，循环结束后，只需判断每一只奶牛的数量是否相等即可
代码如下：
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner in = new Scanner(System.in);
while(in.hasNext()){
int n = in.nextInt();
int a[] = new int [n];
for(int i=0;i<n;i++)
a[i] = in.nextInt();
int mi = min(a);
int ma = max(a);
int count=0;
while(a[ma]-a[mi]>2){
a[ma]-=2;
a[mi]+=2;
count++;
mi = min(a);
ma = max(a);
}
int temp = a[0];
boolean b = true;
for(int i=1;i<n;i++){
if(a[i]!=temp){
b = false;
break;
}
}
if(b)
System.out.println(count);
else
System.out.println(-1);
}
}
public class Main{
public static void main(String[] args){
Scanner in = new Scanner(System.in);
while(in.hasNext()){
int n = in.nextInt();
int a[] = new int [n];
for(int i=0;i<n;i++)
a[i] = in.nextInt();
int mi = min(a);
int ma = max(a);
int count=0;
while(a[ma]-a[mi]>2){
a[ma]-=2;
a[mi]+=2;
count++;
mi = min(a);
ma = max(a);
}
int temp = a[0];
boolean b = true;
for(int i=1;i<n;i++){
if(a[i]!=temp){
b = false;
break;
}
}
if(b)
System.out.println(count);
else
System.out.println(-1);
}
}
//找出最少苹果的奶牛的下标
static int min(int []a){
int min = a[0];
int index=0;
for(int i=1;i<a.length;i++){
if(a[i]<min){
min = a[i];
index = i;
}
}
return index;
}
static int min(int []a){
int min = a[0];
int index=0;
for(int i=1;i<a.length;i++){
if(a[i]<min){
min = a[i];
index = i;
}
}
return index;
}
//找出最多苹果的奶牛的下标
static int max(int []a){
int max = a[0];
int index=0;
for(int i=1;i<a.length;i++){
if(a[i] > max){
max = a[i];
index = i;
}
}
return index;
}
}
static int max(int []a){
int max = a[0];
int index=0;
for(int i=1;i<a.length;i++){
if(a[i] > max){
max = a[i];
index = i;
}
}
return index;
}
}
发表于 2018-08-26 21:58:23
回复(0)
n=int(input().strip())
values=list(map(int,input().strip().split(' ')))
##判断不会出现该种情况的事情,考虑三点：1.苹果是否能够被平分，2每个人手上的苹果是否能2个苹果运送达到平均
#一共需要运送的苹果除以2即为最少的运送次数
def judge(values):
a,b=0,0
for i in values:
if i%2==0:
a +=1
else:
b +=1
return a,b
sum1=sum(values)
div=sum1/n
a,b=judge(values)
result=0
if div==int(div) and div%2==0 and a==n:
for k in values:
res=k-div
if res<=0: continue
else: result +=res
cnt=int(result/2)
print(cnt)
elif div==int(div) and div%2!=0 and b==n:
for k in values:
res=k-div
if res<=0: continue
else: result +=res
cnt=int(result/2)
print(cnt)
else:
print(-1)
发表于 2018-07-31 14:04:50
回复(0)
python3(给自己留个代码)
x = int(input())
y = list(map(int,input().split()))
m=[]
j=0
flag=0 #标志位，实际运行的时候说直通过80%，因为多输出了无效的j。。
n=sum(y)
#n = n / x
if n % x != 0: //判断平均数是否为整数
print(-1)
else:
n = n // x
for i in range(x):
if ((abs(y[i]-n))%2) != 0: //判断每只牛的苹果数与平均数的差值是否为偶数
print(-1)
flag=1
break
else:
m.append(((abs(y[i]-n))) // 2) //计算每只牛的苹果数与平均数的差值是2的几倍
j = j + m[i]
if flag == 0:
print(j // 2) //最后需要除以2，因为计算的总和算了2遍2的倍数
y = list(map(int,input().split()))
m=[]
j=0
flag=0 #标志位，实际运行的时候说直通过80%，因为多输出了无效的j。。
n=sum(y)
#n = n / x
if n % x != 0: //判断平均数是否为整数
print(-1)
else:
n = n // x
for i in range(x):
if ((abs(y[i]-n))%2) != 0: //判断每只牛的苹果数与平均数的差值是否为偶数
print(-1)
flag=1
break
else:
m.append(((abs(y[i]-n))) // 2) //计算每只牛的苹果数与平均数的差值是2的几倍
j = j + m[i]
if flag == 0:
print(j // 2) //最后需要除以2，因为计算的总和算了2遍2的倍数
发表于 2018-07-17 22:03:56
回复(0)
这题其实有两个大判断点，1.输入苹果的总数不能整除牛，输出-1..... 2.只要输入中存在奇偶性不一致的任何一项则可直接输出-1（即输入必须全奇数或全偶数）
最后判断移动数时只要计算苹果数组中小于平均值的项与平均数的差值总和除以2即可（因为有少于平均数的牛，必定会有多于他的牛去给他填补，具体是谁给他填补其实不用管）
#include <iostream>
using namespace std;
int main() {
int n = 0;
int count = 0;
int flag0 = 0, flag1 = 0, sum = 0;
while (cin >> n){
int *p = new int[n];
for (int i = 0; i < n; ++i){
cin >> p[i];
count += p[i];
if (p[i] % 2)
++flag1;
else
++flag0;
}
if (0 != count%n)//第一个大判断：能否整除
cout << -1 << endl;
else{
int average = count / n;
if(flag0*flag1)//第二个大判断：奇偶性是否一致
cout << -1 << endl;
else{
for (int i = 0; i < n; ++i){
if (p[i] < average){
sum += (average - p[i]);//每一个小于平均值项与平均值差值总和
}
}
cout << sum / 2 << endl;//每次移动两个，除以2
count = 0; flag0 = 0; flag1 = 0; sum = 0; delete []p;//清空，为下一次输入初始化
}
}
}
return 0;
}
编辑于 2018-07-03 16:00:39
回复(0)
问题信息
通过挑战的用户
查看代码-
2022-09-14 11:16:46
-
2022-09-12 10:41:33 -
2022-09-10 10:50:05
-
2022-09-09 20:20:54
-
2022-09-09 12:32:35
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
