面试经典150题 P502 IPO

---

时间轴

时间轴

2025-12-08

init

堆排序

---

题目：

P502 IPO

https://leetcode.cn/problems/ipo/?envType=study-plan-v2&envId=top-interview-150

堆排序，每次把小于等于当前资本的所有利润放入堆中，取最大值，然后更新资本，重复以上操作，直到进行了 k 次或没有项目可投。

#include <vector>
#include <unordered_map>
#include <utility>
#include <algorithm>
#include <queue>

using std::vector;
using std::unordered_map;
using std::pair;
using std::priority_queue;

class Solution {
    public:
        int findMaximizedCapital(int k, int w, vector<int> &profits,
                                 vector<int> &capital)
        {
                int n = profits.size();
                int i, selected = 0;

                vector<pair<int, int> > prof2cap;

                for (i = 0; i < n; i++) {
                        prof2cap.push_back({ profits[i], capital[i] });
                }

                std::sort(prof2cap.begin(), prof2cap.end(),
                          [](pair<int, int> &l, pair<int, int> &r) {
                                  return l.second < r.second;
                          });
                priority_queue<int> profit_heap;

                i = 0;
                while (k--) {
                        // 把所有capital小于w的加入堆
                        while (i < n && prof2cap[i].second <= w) {
                                profit_heap.push(prof2cap[i++].first);
                        }

                        if (profit_heap.empty()) {
                                break;
                        }

                        w += profit_heap.top();
                        profit_heap.pop();
                }
                return w;
        }
};