美文网首页
[笔试题]分糖果

[笔试题]分糖果

作者: 二二二二呆 | 来源:发表于2018-05-12 22:05 被阅读0次

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

    相关文章

      网友评论

          本文标题:[笔试题]分糖果

          本文链接:https://www.haomeiwen.com/subject/wtahdftx.html