题意

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

解法1：暴力

如果有一堆元素不小于 ，那它们的平均值一定不小于 。可以枚举所有子集，分别计算平均值。

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 最多有多少数字不小于x
     * @param n int整型 
     * @param x int整型 
     * @param a int整型vector 
     * @return int整型
     */
    int arrange(int n, int x, vector<int>& a) {
        // write code here
        int ret=0;
        for(int s=1; s<(1<<n); ++s){ // 枚举子集
            long long sum=0;
            int cnt=0;
            for(int i=0; i<n; ++i){
                if(s&(1<<i)){
                    sum+=a[i];
                    ++cnt;
                }
            }
            if(sum>=1ll*cnt*x) ret=max(ret, cnt);
        }
        return ret;
        return n;
    }
};

复杂度分析

空间复杂度：不需要额外空间，
时间复杂度：枚举子集并统计，对每个子集需要扫描所有元素进行统计，

解法2：排序

只需要看最大的一部分元素的平均值即可。
可以将元素从小到大排序，从后往前统计后缀和，依次检验后缀平均值是否小于 。最后一个不小于 的后缀长度即为答案。

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 最多有多少数字不小于x
     * @param n int整型 
     * @param x int整型 
     * @param a int整型vector 
     * @return int整型
     */
    int arrange(int n, int x, vector<int>& a) {
        // write code here
        sort(a.begin(), a.end());
        long long sum=0;
        for(int i=n-1; i>=0; --i){
            sum+=a[i];
            if(sum<1ll*x*(n-i)) return n-i-1;
        }
        return n;
    }
};

复杂度分析

空间复杂度
时间复杂度