讨论/技术交流/一道leetcode失传的题目~/
一道leetcode失传的题目~

71619411502_.pic.jpg

当时难度为中等。

3
共 16 个回复
class Solution {
public:
    int minAverageBudget(vector<int>& people, vector<int>& budget, int num) {
        int left = INT_MAX, right = 0;
        for (int i = 0; i < people.size(); ++i) {
            int temp = ceil((double)budget[i] / people[i]);
            if (left > temp) left = temp;
            if (right < temp) right = temp;
        }
        while (left < right - 1) {
            int mid = (right - left >> 1) + left;
            if (canPay(people, budget, num, mid)) right = mid;
            else left = mid + 1;
        }
        return canPay(people, budget, num, left) ? left : right;
    }
    bool canPay(const vector<int>& people,const vector<int>& budget, int num, int average) {
        priority_queue<int,vector<int>, greater<int>> q;
        for (int i = 0; i < people.size(); ++i) {
            q.push(average * people[i] - budget[i]);
        }
        int remain = 0;
        for (int i = 0; i < num; ++i) {
            remain += q.top();
            q.pop();
        }
        return remain >= 0;
    }
};
2

比如,1 10000 10000,0.5 10000 20000,按你的做出来平均值为1.5,但是最大平均值约为1.9999

2

01分数规划,力扣人都知道贪心不行

1

为什么贪心不对?

1
class Solution :
    def minAverageBudget(self, people: list[int], budget: list[int], num: int) -> int :
        left,right,best = 0,2147483647,2147483647
        
        def check(x) :
            A = sorted([people[i]*x-budget[i] for i in range(len(people))])
            return sum(A[:num])>=0
        
        while left<=right :
            mid = (left+right)//2
            if check(mid) :
                best = mid
                right = mid-1
            else :
                left = mid+1
        
        return best

是否可以考虑,按人数分组,组内排序,最后 优先队列

10 100 b/p分值为10
10000 10000 b/p分值为1
2 1 b/p分值为0.5
选1 3是更好的
大概意思就是,除了budget/people最大的,其他再大也是拖了后腿。所以说少拖一点后腿会更好一点

大意了 确实不对

哈哈,是啊,大佬麻烦给个反例。

偶然做到这题,过几天来看发现消失了。。还好留了截图。。就觉得这题挺好的,据说在竞赛里是模版题。