牛牛的分配题解

题意：在牛牛面前有n个瓶子，每个瓶子的大小体积都一样，但是每个瓶子内的含水量都不相同。
因为牛牛是个完美主义者，他希望瓶子中的水能够满足他的要求，他的要求是瓶子中的水最少为x。所以他打算对这些瓶子里的水进行重新分配，以满足最多的瓶子中水量大于等于x。
牛牛的分配规则是：每次可以选择多个瓶子，将里面的水平均分配到已选择的瓶子中。
给定n个瓶子和牛牛的对瓶中的水量要求x，以及n个瓶子中的含水量，求最多可以有多少个瓶子满足牛牛的要求？

时间复杂度: 空间复杂度:

解题思路：
此题如果纯暴力去搜索的话，复杂度会达到 ,该代码很容易实现，但容易超时，故不是最优解。
换种思路思考，寻找一个贪心策略，我们可以对数组进行从大到小排序，令a[i] = a[i] + a[i-1],这样我们可以得到当前下标前所有瓶子水量的和，然后根据分配策略，去寻找最多的瓶子的水量大于x，不过这样的话，空间复杂度会达到 ，也不是很好。
我们可以再优化一下，利用一种类似于生活中常见的多退少补的思想，先进行从大到小的排序，将大于x的值的和都求出来，然后去尽可能的补上小于x的值，这样的分配策略就可以求出最多的瓶子的数量，而且空间复杂度也可以降到 。
将上述想法，以代码的方式实现，如下：

int cmp(int a, int b)
{
    return a > b;
}
/**
 * 返回重新分配后，满足牛牛要求的水量的瓶子最多的数量
 * @param n int整型 瓶子的数量
 * @param x int整型 牛牛的对瓶中的水量要求
 * @param a int整型vector 每个瓶子中的含水量
 * @return int整型
 */
int solve(int n, int x, vector<int> &a)
{
    // write code here
    long long sum = 0;
    sort(a.begin(), a.end(), cmp); //自大到小排序
    int i, j = -1;
    for (i = 0; i < n; i++)
    {
        if (a[i] >= x)
            sum += a[i] - x;
        else
        {
            j = i;
            break;
        }
    }
    if (j == -1)
    {
        return n;
    }
    for (i = j; i < n; i++)
    {
        if (sum >= x - a[i])
            sum -= x - a[i];
        else
            break;
    }
    return i;
}

我们可以根据以上的思路，把代码继续精简一下，可以想到，先将瓶子按水量递减排序，使用多退少补的思想，用水多的瓶子去平均，水少的瓶子对当前的分配策略来说是一种“累赘”，越往右平均，平均后瓶子中的水量始终是小于等于平均前的水量的，一句话总结：平均到不能平均就退出。即：当前缀和÷瓶子数小于x的时候退出即可。

/**
 * 返回重新分配后，满足牛牛要求的水量的瓶子最多的数量
 * @param n int整型 瓶子的数量
 * @param x int整型 牛牛的对瓶中的水量要求
 * @param a int整型vector 每个瓶子中的含水量
 * @return int整型
 */
int solve(int n, int x, vector<int> &a)
{
    // write code here
    sort(a.rbegin(), a.rend());
    long long sum = 0;
    for (int i = 0; i < n; i++)
    {
        sum += a[i];
        if (sum * 1.0 / (i + 1) < x)
            return i;
    }
    return n;
}