LeetCode-502 IPO

Description

有\(n\)个项目，每个项目可以获得利润\(p_i\)，但需要前提资本\(c_i\)才能启动。初始时你有资本\(w\)，求最多\(k\)个项目的最大利润

Constraints

时间复杂度不超过\(O(nlogn)\)

Solution

这种一眼是排序+堆操作的贪心，最近品鉴得有点多了。排序按能合法操作的来，堆按所求最优的做关键字，因此是按资本排序，并用利润作为大根堆关键字

剩下的就是一个模拟过程（这点有别于反悔操作）

Code

class Solution {
public:
    int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {
        auto &pro = profits;
        auto &cap = capital;
        using Tup = tuple<int, int>;
        vector<Tup> vec;
        for(size_t i = 0; i < pro.size(); ++i) {
            vec.emplace_back(cap[i], pro[i]);
        }
        sort(vec.begin(), vec.end());
        priority_queue<int> pq;
        for(size_t i = 0; i < vec.size();) {
            bool any_op = false;
            while(i < vec.size() && w >= get<0>(vec[i])) {
                pq.emplace(get<1>(vec[i]));
                any_op = true;
                i++;
            }
            if(k && !pq.empty()) {
                w += pq.top();
                pq.pop();
                any_op = true;
                k--;
            }
            if(!any_op) break;
        }
        // Note
        while(k-- && !pq.empty()) w+=pq.top(), pq.pop();
        return w;
    }
};

Link

LeetCode-502 IPO