【牛客编程巅峰赛S1第8场】牛牛的分配

题目

给定 n 个瓶子以及 n 个瓶子中的含水量，牛牛要求瓶子中的水最少为 x，所以他打算对这些瓶子里的水进行重新分配。
牛牛的分配规则是：每次可以选择多个瓶子，将里面的水平均分配到已选择的瓶子中。
求最多可以有多少个瓶子满足牛牛的要求？

解题思路

按瓶子中的含水量从大到小对瓶子序列 进行排序。从头到尾遍历瓶子。

• 如果瓶子的含水量 ，满足要求， 加一，并将多余的水 累加计入 中。
• 如果瓶子的含水量 ，判断剩余的水加当前瓶子中的水是否满足要求，
  如果满足， 加一，剩余水量为 ；否则，跳出循环，因为后面的瓶子含水量更少。

最后，返回 。

C++代码

class Solution {
public:
    /**
     * 返回重新分配后，满足牛牛要求的水量的瓶子最多的数量
     * @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());
        int cnt = 0;
        int remain = 0;
        for(auto k : a){
            if(k >= x){
                ++cnt;
                remain += k - x;
            }
            else{
                if(remain + k >= x){
                    ++cnt;
                    remain -= x - k;
                }
                else
                    break;
            }
        }
        return cnt;
    }
};