题解 | #牛牛的分配#

题意整理

给定长度为n的数组，将数字大的分配给数字小的，使得尽可能多的数不小于给定数字x。
求最多有多少个数不小于x。

方法一（排序+模拟）

1.解题思路

首先初始化结果变量和分配之后多余的数。
将给定数组排序，逆序遍历，保证每次访问的都是当前最大的，如果大于等于x，说明能分配，则计数加一，并加上对应剩余数。如果小于x，但是剩余数加上当前数字大于等于x，还是能分配，计数加一，减去对应剩余数；否则不能分配，直接终止循环。

动图展示：
图片说明

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 最多有多少数字不小于x
     * @param n int整型 
     * @param x int整型 
     * @param a int整型一维数组 
     * @return int整型
     */
    public int arrange (int n, int x, int[] a) {
        //初始化结果变量和剩余分配数
        int res=0;
        int remain=0;
        //排序
        Arrays.sort(a);
        for(int i=n-1;i>=0;i--){
            //如果当前数大于x，一定可分配，res加一，同时计算剩余可分的
            if(a[i]>=x){
                remain+=a[i]-x;
                res++;
            }
            else{
                //如果当前数小于x，但是加上剩余数后，大于等于x，则还是可分配
                if(remain>=x-a[i]){
                    remain-=x-a[i];
                    res++;
                }
                //否则，不能再分配
                else{
                    break;
                }
            }
        }
        return res;
    }
}

3.复杂度分析

时间复杂度：排序的时间复杂度为 $O(nlog_2n)$ ，循环是线性的，复杂度为 $O(n)$ ，所以时间复杂度为 $O(nlog_2n)$ 。
空间复杂度：需要额外常数级别的空间，所以空间复杂度为 $O(1)$ 。

方法二（排序+按平均数试探）

1.解题思路

首先初始化结果变量和累加和。
将给定数组排序，逆序遍历，统计当前访问到的所有数的累加和，计算出平均数，如果大于等于x，说明可分配，计数加一；否则，终止循环。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 最多有多少数字不小于x
     * @param n int整型 
     * @param x int整型 
     * @param a int整型一维数组 
     * @return int整型
     */
    public int arrange (int n, int x, int[] a) {
        //初始化结果变量和累加和
        long res=0;
        long sum=0;
        //排序
        Arrays.sort(a);
        //逆序遍历
        for(int i=n-1;i>=0;i--){
            //统计累加和
            sum+=a[i];
            //当前平局数
            long avg=sum/(n-i);
            //如果大于等于x，说明可分配
            if(avg>=x){
                res++;
            }
            //否则终止循环
            else{
                break;
            }
        }
        return (int)res;
    }
}

3.复杂度分析

时间复杂度：排序的时间复杂度为 $O(nlog_2n)$ ，循环是线性的，复杂度为 $O(n)$ ，所以时间复杂度为 $O(nlog_2n)$ 。
空间复杂度：需要额外常数级别的空间，所以空间复杂度为 $O(1)$ 。