[笔试题]分糖果

科大讯飞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);
    }
    }