牛牛的分配

长度为$nn$n的数组，每次可以选这若干元素使元素的值变味这些元素的和的平均值，给出数组的数字$xx$x，求经过操作数组中最多有多少个数字不小于$xx$x

案例：
输入: 3,7,[9,4,9]
输出: 3 一开始有3个数字，分别为9，4，9，x为7操作这3个数字后每个数字都不小于x

方法一： 排序

元素从大到小排序，每次选取最大的值加到总和中如果加入当前值后平均数小于x则说明添加后面的数也无法大于x

class Solution {
public:
    int arrange(int n, int x, vector<int>& a) {
        // write code here
        sort(a.begin(), a.end(), [&](int a, int b){
           return a > b; 
        });
        long long sum = 0; //统计总和
        for(int i = 0; i < n; i ++){
            sum += a[i]; 
            if(!(sum / (i + 1) >= x)) return i; //如果平均小于等于x的就返回位置
        }
        if(sum / n >= x) return n; //如果最后所有都大于等于x则n就是答案
        return 0;
    }
};

时间复杂度: $O\left(nlogn\right)O(nlogn)$O(nlogn)排序的复杂度
空间复杂度: $O\left(1\right)O(1)$O(1) 使用若干个变量

方法二: 排序+按平均值计数

与方法一思路一致在求解过程中使用平均值判断并计数

class Solution {
public:
    int arrange(int n, int x, vector<int>& a) {
        // write code here
        sort(a.begin(), a.end(), [&](int a, int b){ //c从大到小排序
            return a > b;
        });
        long long sum = 0; //计算平均值大于x的总和
        int cnt = 0; //统计有多少个数
        for(int i = 0; i < a.size(); i ++){
            if(a[i] >= x){ // 如果当前值大于x则算上平均没有影响
                cnt ++;
                sum += a[i];
            }else{
                if((sum + a[i]) / (cnt + 1) >= x){ //如果加上总平均值大于x则添加
                    cnt ++;
                    sum += a[i];
                }else break;
            }
        }
        return cnt;
    }
};

时间复杂度: $O\left(nlogn\right)O(nlogn)$O(nlogn)排序的复杂度
空间复杂度: $O\left(1\right)O(1)$O(1) 使用若干个变量