N个人，按M进行分组

布满荆棘的人生 2022-12-20 05:49 193阅读 0赞

题目：一公司新招N个人，按M进行分组。每一组将单独进行培训，组与组之间不能交流，由此引发一个问题：同一组的每个人相互之间都会成为朋友，而不同组的人相互之间不能成为朋友（培训期间）。如果第i组有a\[i\]个人，那么这一组将会有b\[i\]=a\[i\]\*(a\[i\]-1)/2对朋友。请问如何分组才能使得b\[i\]的和最大，又如何分组才能使得b\[i\]的和最小呢？  
输入N,M两个正整数（1<=m<=n<=10 0000 0000）  
输出b\[i\]和最小值及b\[i\]和最大值，用空格分开。

public static String resultSum(int n, int m) { 
            if (n < m) { 
                return null;
            }
            //n个人 m个分组
            int maxSum = 0;//b[i]和的最大值
            int minSum = 0;//b[i]和的最小值
    
            //sum 最大值时 n-m+1 这一组人数最多，其它组人数都为1
            maxSum = (n - m + 1) * (n - m + 1 - 1) / 2;
    
            //minSum最小值时，每个组分得人数跟平均数最接近n/m
            Boolean isAliquot = n % m == 0 ? true : false; // 判断n/m是否能整除 能整除true 不能整除false
            if (isAliquot) { 
                minSum = (n / m) * (n / m - 1) / 2 * m;//如果能整除，说明n个人可以平均地分成m组，则每组有n/m个人，当前组则有(n/m)*(n/m-1)/2对朋友，最小值为：当前组的多少对朋友*m组
            } else { 
                //如果不能整除时
                int average = n / m; //每组平均数，这里会存在向下取整，所以平均数会小
                int[] mm = new int[m]; //定义 一个数组表示，每组的人数
                for (int i = 0; i < mm.length; i++) { 
                    mm[i] = average;//初始化数组
                }
    
                int differ = n - average * m;//相差多少
                for (int i = 0; i < differ; i++) { 
                    mm[i]++; //把相差的数加回来
                }
    
                //计算minSum
                for (int i = 0; i < mm.length; i++) { 
                    minSum += mm[i] * (mm[i] - 1) / 2;
                }
            }
            //sum 最小值时 n/m
            return minSum + " " + maxSum;
        }