科大讯飞2018实习生笔试题:
/**
- 分糖果:有一盒糖果要分成两份,但是每颗糖果质量不尽相同,为了分配公平,两份糖果数量相差不得超过1,
- 在此条件下,如何使两份糖果质量相差最小。(糖果数不大于20,糖果质量在1-450之间)
- <p>
- 输入:
- 5 9 6 5 8 7 10
- (第一个数表示这份糖果的个数,后面每个数字表示每颗糖果的质量)
- 输出:
- 17,18(若两份糖果质量不同,质量小的在前面)
*/
思路:
- 首先求数组a[n]和的平均数,比如根据样例,输入5个数,分别是 9 6 5 8 7 10,那这5个数的和为35,avg = 35/2 = 17,根据平均值把糖果分成两份;
- 把数组从下到大排序,sum += a[i] ,数组从小到大(从左到右)加和,一旦加到第i个数,sum超过avg了,那把这第i个数记录下来。
- 数组左边的数加和小于avg,但是加上a[i]会超过avg;同样,数组中a[i]元素右边的所有数加和也小于avg,但是加上a[i]会超过avg。那么我们就比较leftSum 和 rightSum哪个距离avg更远,把a[i]加给那个更远的就可以了。
代码
import java.util.Arrays;
import java.util.Scanner;
public class Candy {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] q = new int[n];
for (int i = 0; i < n; i++) {
q[i] = sc.nextInt();
}
printQ(q);
}
public static void printQ(int[] q) {
Arrays.sort(q);
int sum = 0;//数组加和
int avg = 0;//数组平均值
int left = 0;//数组从左边的加和
int right = 0;//数组从右边加和
int midNum = 0;//中心数字
//计算sum
for (int i = 0; i < q.length; i++) {
sum += q[i];
}
//计算avg
avg = sum / 2;
//数组从小到大加和(从左向右加和)
for (int i = 0; i < q.length; i++) {
left += q[i];
//一旦加了a[i]大于avg了,记录a[i]
if (left > avg) {
midNum = q[i];
left -= midNum;
break;
}
}
//相应的,a[i]右边的数加和
right = sum - left - midNum;
//计算结果(距离远的加上a[i],也就是midNum)
int result1 = distance(left, right, avg, midNum);
int result2 = sum - right;
//判断两个数哪个大
int maxOne = max(result1, result2);
int minOne = min(result1, result2);
System.out.println(minOne + "," + maxOne);
}
private static int min(int result1, int result2) {
return (result1 < result2) ? result1 : result2;
}
private static int max(int result1, int result2) {
return (result1 > result2) ? result1 : result2;
}
/**
* 比较left 和 right哪个离avg更远,把midNum赋给更远的那个
*
* @param left
* @param right
* @param avg
* @param midNum
* @return
*/
private static int distance(int left, int right, int avg, int midNum) {
return (avg - left) >= (avg - right) ? (left + midNum) : (right + midNum);
}
}
网友评论