1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

class Solution
{
public:
    int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital)
    {
        int n = profits.size();
        std::vector<std::pair<int, int>> projects;

        // 将项目的启动资本和利润配对，并按启动资本排序
        for (int i = 0; i < n; ++i)
            projects.push_back({capital[i], profits[i]});
        std::sort(projects.begin(), projects.end());

        // 最大堆，用来存放前资本 w 可以启动的所有项目的利润
        std::priority_queue<int> heap;
        int i = 0;

        // 完成最多 k 个项目
        while (k--)
        {
            // 将所有可以启动的项目的利润加入堆
            while (i < n && projects[i].first <= w)
                heap.push(projects[i++].second);

            // 如果堆为空，表示没有可用的项目，退出
            if (heap.empty())
                break;

            // 从堆中选择利润最大的项目并完成
            w += heap.top();
            heap.pop();
        }

        return w;
    }
};