IPO (Initial Public Offering) trong C++

Công ty có vốn ban đầu W. Có thể làm tối đa k dự án. Dự án i cần vốn Capital[i] cho lợi nhuận Profits[i]. Tối đa hóa vốn sau ≤ k dự án.

Ví dụ

k=2, W=0, Profits=[1,2,4], Capital=[0,1,1] → 5 (làm dự án 0 rồi dự án 2).

Thuật toán 2 Priority Queue

1. pqCapital (min-heap theo capital): tất cả dự án.
2. pqProfit (max-heap theo profit): dự án khả thi (capital ≤ W).
3. Lặp k lần: chuyển dự án khả thi từ pqCapital sang pqProfit, chọn dự án profit lớn nhất, cập nhật W.

Chương trình C++

#include <bits/stdc++.h>
using namespace std;

struct CapCmp { bool operator()(pair<int,int> a, pair<int,int> b){ return a.second > b.second; } };

class Solution {
public:
    int findMaximizedCapital(int k, int W, vector<int>& Profits, vector<int>& Capital) {
        priority_queue<pair<int,int>, vector<pair<int,int>>, CapCmp> pqCap;
        priority_queue<pair<int,int>> pqProf;
        for(int i=0;i