[编程题]分苹果
- 热度指数：54918 时间限制：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
思路很简单，先按条件过滤：(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.util.*;
public class Main{
public static void main (String[] args) {
Scanner cin = new Scanner(System.in);
int num = cin.nextInt();
int[] nums = new int[num];
for (int i = 0; i < num; i++) {
nums[i] = cin.nextInt();
}
// 数学方法解决
System.out.println(resolve(nums));
}
private static int resolve(int[] nums) {
// 总数
int sum = 0;
// 平均数
int average = 0;
for (int num : nums) {
sum += num;
}
// 如果无法整除
if (sum % nums.length != 0) {
return -1;
}
// 如果整除后的结果与原数组中的奇偶性不一致
if(sum/nums.length%2!=nums[0]%2){
return -1;
}
// 判断每个数是否同为奇数或者同为偶数
for (int i = 0; i < nums.length; i++) {
if (nums[i]%2!=nums[0]%2){
return -1;
}
}
average = sum / nums.length;
int count = 0;
// 计算每个数要到达平均数的次数，全部加起来然后除以4
for (int num : nums) {
count += Math.abs(num - average);
}
return count / 4;
}
}
发表于 2021-09-09 20:48:40
回复(0)
import java.util.Arrays;
import java.util.Scanner;
// 思路：先算总和记平均值，如果除不尽，返回-1，
// 如果平均值为奇数但是数组里有偶数，返回-1，如果数组里有奇数，平均值为偶数返回-1；
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int num = scanner.nextInt();
int[] arr = new int[num];
for (int i = 0; i < num; i++) {
arr[i] = scanner.nextInt();
}
System.out.println(divideApples(arr));
}
private static int divideApples(int[] arr) {
if (arr.length == 0) {
return -1;
}
if (arr.length == 1) {
return 0;
}
int sum = 0; // 苹果总数
int sin = 0; // 奇数总数
int dou = 0; // 偶数总数
for (int i = 0; i < arr.length; i++) {
if (arr[i]%2 == 1) {
sin++;
} else {
dou++;
}
sum+=arr[i];
}
if (sum%arr.length!=0) {
return -1;
}
int average = sum/arr.length;
if (average%2==0&&sin>0) {
return -1;
}
if (average%2==1&&dou>0) {
return -1;
}
int count = 0; // 转移次数
Arrays.sort(arr);//先排序
int i = arr.length - 1;
int j = 0;
while (i>j) {
while (arr[i] > average && arr[j] < average) {
arr[i]-=2;
arr[j]+=2;
count++;
}
if (arr[i]==average) {
i--;
}
if (arr[j] == average) {
j++;
}
}
return count;
}
}
发表于 2021-05-07 14:20:24
回复(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)
这个确实要是能想到捷径就很简单。首先，如果苹果总数不能整除奶牛数量，或者每只奶牛有的苹果数量和平均数之间的差不能被2整除都是返回-1。剩下的，只需要将每只多出平均数的奶牛拥有的苹果与平均数之间的差加在一起然后除以2，得到的就是需要移动苹果的次数。
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] cow = new int[n];
for(int i = 0;sc.hasNext();i++){
cow[i] = sc.nextInt();
}
int sum = 0;
for(int j = 0;j<cow.length;j++){
sum+=cow[j];
}
int avg = 0;
int k = -1;
if(sum%cow.length!=0){
System.out.println(k);
return;
}
avg = sum/cow.length;
for(int i:cow){
if((i-avg)%2!=0){
System.out.println(k);
return;
}
}
int apple = 0;
int c = 0;
for(int i:cow){
c = i-avg;
if(c>0)
apple += c;
}
k = apple/2;
System.out.println(k);
}
}
发表于 2020-09-02 00:37:02
回复(0)
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
int n = sc.nextInt();
int[] arr = new int[n];
int sum = 0;
for(int i = 0; i < n; i++){
arr[i] = sc.nextInt();
sum += arr[i];
}
boolean flag = true;
flag &= sum % n == 0;
int res = 0;
if(flag){
int temp = sum / n;
for(int i = 0; i < n; i++){
if((arr[i] - temp) % 2 != 0){
flag = false;
break;
}else{
if(arr[i] - temp >= 0){
res += (arr[i] - temp) / 2;
}
}
}
}
System.out.println(flag ? res : -1);
}
}
}
发表于 2020-08-16 15:06:53
回复(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)
/**看了前几名的解答方法都是比较有技巧性的，我是直接用的贪心算法的思路， 没那么多的技巧性，大家可以看看。贪心决策ru 1.把数据排序(小->大) 2.每次把当前最大的数-2 最小的数+2；移动次数+1 3.加减过程中，如果最小的数出现>平均值或最大的数小于平均值，直接返回-1；
import java.util.Arrays;
import java.util.Scanner;
/**
* @author JT.L
* @date 2019/8/28 20:54:53
* @description
*/
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()) {
int n = Integer.parseInt(scanner.nextLine());
String[] strings = scanner.nextLine().split(" ");
int[] a = new int[strings.length];
for (int i = 0; i < strings.length; i++) {
a[i] = Integer.parseInt(strings[i]);
}
System.out.println(solution(a));
}
}
private static int solution(int[] a) {
int moveTimes = 0;
int failure = -1;
int moveApple = 2;
Arrays.sort(a);
int average = 0;
for (int i = 0; i < a.length; i++) {
average += a[i];
}
// 不能整除人数 返回-1
if (average%a.length!=0){
return failure;
}
average /= a.length;
for (int i = 0, j = a.length - 1; i < j; ) {
while (a[i] != average) {
if (a[i] > average || a[j] < average) {
return failure;
}
if (a[j] > average) {
a[i] += moveApple;
a[j] -= moveApple;
moveTimes++;
} else if (a[j] == average) {
j--;
}
}
i++;
}
return moveTimes;
}
}
发表于 2019-08-28 21:36:52
回复(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)
import java.util.Arrays;
import java.util.Scanner;
public class Main {
//判断数组是否同为奇数或者同为偶数
public boolean Ifthesame(int []a) {
for(int i = 1;i<a.length;i++) {
if (a[i]%2!=a[i-1]%2) {
return false;
}
}
return true;
}
public int GetResult(int n,int []coat,int sum) {
int more = 0;
if(sum%n==0&&Ifthesame(coat)) {
for(int i = n-1;coat[i]>sum/n;i--)
more+=coat[i]-sum/n;
return more/2;
}
return -1;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
while (in.hasNext()) {
int sum = 0;
int []coat = new int[n];
for(int i = 0;i<n;i++) {
coat[i] = in.nextInt();
sum+=coat[i];
}
Arrays.sort(coat);
Main test = new Main();
System.out.println(test.GetResult(n, coat,sum));
}
}
}
import java.util.Scanner;
public class Main {
//判断数组是否同为奇数或者同为偶数
public boolean Ifthesame(int []a) {
for(int i = 1;i<a.length;i++) {
if (a[i]%2!=a[i-1]%2) {
return false;
}
}
return true;
}
public int GetResult(int n,int []coat,int sum) {
int more = 0;
if(sum%n==0&&Ifthesame(coat)) {
for(int i = n-1;coat[i]>sum/n;i--)
more+=coat[i]-sum/n;
return more/2;
}
return -1;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
while (in.hasNext()) {
int sum = 0;
int []coat = new int[n];
for(int i = 0;i<n;i++) {
coat[i] = in.nextInt();
sum+=coat[i];
}
Arrays.sort(coat);
Main test = new Main();
System.out.println(test.GetResult(n, coat,sum));
}
}
}
发表于 2018-09-11 16:10:10
回复(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)
import java.util.Scanner;
public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n=scanner.nextInt(); int[] array=new int[n]; array[0]=scanner.nextInt(); int sum=array[0]; for(int i=1;i<n;i++){ array[i]=scanner.nextInt();
//第一个条件：所有数的奇偶性必须是一样的 if(((array[i-1]^array[i])&1)==1){ System.out.println(-1); return; } sum+=array[i]; }
//第二个条件：n能够整除sum if(sum%n!=0){ System.out.println(-1); return; } int average=sum/n;
//第三个条件：均值的奇偶性和数的奇偶性相同 if(((array[0]^average)&1)==1){ System.out.println(-1); return; } int differ=0; for(int i=0;i<n;i++){ differ+=Math.max(0, average-array[i]); } System.out.println(differ/2); }
}
发表于 2018-08-24 23:15:12
回复(0)
分享一个超简单的思路：
首先要明确一点：所有苹果的总数加起来应该可以整除奶牛的数量，否则怎么分都不可能平均。
以这个作为前提，那么每只奶牛(当前的苹果数-平均数)/2即为移动的次数，只有当加苹果的次数等于捡苹果的次数，才算有解。
```
import java.util.ArrayList; import java.util.Scanner; public class Main { public static void main(String args[]) { Scanner input = new Scanner(System.in); while (input.hasNextInt()) { int n = input.nextInt(); //若只有一只奶牛，则移动0次获得平均 if (n == 1) { System.out.println(0); break; } ArrayListInteger> list = new ArrayList(n); for (int i = 0; i n; i++) { list.add(input.nextInt()); } //求平均值 int average = list.stream().mapToInt(x -> x).sum() / n; //加苹果的次数 int addCount = 0; //减苹果的次数 int reduceCount = 0; for (Integer integer : list) { if (integer > average) { addCount += (integer - average) / 2; } else if (integer average) { reduceCount += (average - integer) / 2; } } if (addCount == reduceCount && addCount != 0) System.out.println(addCount); else System.out.println(-1); } input.close(); } }
发表于 2018-08-13 15:52:54
回复(0)
先计算总和可以均分否？ 再计算差值是否可以均分， 最后计算差值移动次数。public class SplitApple {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int [] num=new int[n];
for(int i=0;i<n;i++){
num[i]=sc.nextInt();
}
splitapple(num,n);
}
private static void splitapple(int[] num, int n) {
int sum=0;
for(int i=0;i<n;i++){
sum+=num[i];
}
//如果加和不均分 则将没有进行的必要
if(sum%n!=0){
System.out.println(-1);
}else{
int apple=sum/n;
Arrays.sort(num);
int time=0;
boolean b=false;
for(int i=0;i<num.length;i++){
// 如果2 个2 个的移动，有余1的情况 ，将不可能 分均
if(Math.abs(apple-num[i])%2==1){
b=true;
break;
}
//所以只有一种情况符合 条件
time+=Math.abs(apple-num[i])/2;
}
if(b){
System.out.println(-1);
}else{
System.out.println(time/2);
}
}
}
}
发表于 2018-07-09 14:31:06
回复(0)
import java.util.*;
public class Main65 {
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
int n=scanner.nextInt();
int[] a=new int[n];
int sum=0;
int count=0;
int[] flag=new int[n];
for(int i=0;i<n;i++) {
a[i]=scanner.nextInt();
sum+=a[i];
}
if(sum%n!=0) {
System.out.println("-1");
}else {
int ave=sum/n;
for(int i=0;i<n;i++) {
if(a[i]<ave) {
flag[i]=1;
}else if(a[i]==ave) {
flag[i]=0;
}else {
flag[i]=-1;
}
}
for(int i=0;i<n;i++) {
if(flag[i]==-1) {
while(a[i]>ave) {
a[i]=a[i]-2;
count++;
}
if(a[i]<ave) {
count=-1;
break;
}
}else if(flag[i]==1) {
while(a[i]<ave) {
a[i]=a[i]+2;
count++;
}
if(a[i]>ave) {
count=-1;
break;
}
}
}
if(count==-1) {
System.out.println(count+"");
}else {
System.out.println(count/2+"");
}
}
}
}
if---else
发表于 2018-06-29 23:00:03
回复(0)
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)
http://www.cnblogs.com/52circle/p/9015810.html
import java.io.IOException;
import java.io.IOException;
import java.util.Scanner;
public class Main {
public static void main(String[] args) throws IOException {
Scanner scanner=new Scanner(System.in);
int n=scanner.nextInt();
int [] a=new int[n];
int sum=0;
for(int i=0;i<n;i++){
a[i]=scanner.nextInt();
sum+=a[i];
}
if (sum%n!=0) {
System.out.println(-1);
return;
}
int x=sum/n;
for (int i = 0; i < a.length; i++) {
if (Math.abs(a[i]-x)%2!=0) {
System.out.println(-1);
return;
}
}
int cout=0;
for (int i = 0; i < a.length; i++) {
if (a[i]<x) {
cout+=(x-a[i])/2;
}
}
System.out.println(cout);
}
}
发表于 2018-05-11 17:07:24
回复(0)
判断分苹果是否必然会失败，判断条件来源有两个：
-
奶牛的苹果数之和无法被奶牛数整除， 或者说每个奶牛的苹果数的平均值不是个整数
-
虽然能通过1.1的条件，但是奶牛间交换的苹果数小于2才能达到平分的结果， 比如1个苹果
如何分苹果
- 把每个奶牛的苹果数放入一个有序的列表中， 每次将最多苹果的奶牛将苹果分给最少苹果的奶牛
- 当在这个有序列表中，最多苹果的奶牛的苹果 == 最少苹果的奶牛的苹果 的时候， 分配结束
import java.util.*;
public class Main {
public static void distributeApple (int cows, ArrayList<Integer> apples) {
int appleSum = 0;
for (int x: apples) {
appleSum+=x;
}
int average = appleSum/cows;
// 分苹果必定失败的第一个判断条件
if (average*cows !=appleSum) {
System.out.println(-1);
return ;
}
// 分苹果必定失败的第二个判断条件
for (int x: apples) {
if ((x - average)%2 !=0) {
System.out.println(-1);
return ;
}
}
// 可以成功， 开始分苹果
int count = 0;
Collections.sort(apples);
while (apples.get(0) != apples.get(apples.size()-1)) {
int min = apples.remove(0);
int max = apples.remove(apples.size()-1);
apples.add(min + 2);
apples.add(max - 2);
Collections.sort(apples);
count++;
}
System.out.println(count);
}
public static void main (String args []) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()) {
int cows = scanner.nextInt();
scanner.nextLine();
String str = scanner.nextLine();
String [] apples = str.split(" ");
ArrayList<Integer> list = new ArrayList();
for (int i=0;i<apples.length;i++) {
list.add(Integer.parseInt(apples[i]));
}
distributeApple(cows,list);
}
scanner.close();
}
}
编辑于 2018-04-30 16:54:27
回复(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群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
