贪心算法,先按照资本准入排序,然后使用最大堆存利润,获取k次利润
ref{:target=”_blank”}
C++ 代码
class Solution {
public:
int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {
vector<pair<int,int>> vecs;
int n = profits.size();
for(int i=0; i<n; ++i) {
vecs.push_back({capital[i], profits[i]});
}
sort(vecs.begin(), vecs.end());
priority_queue<int> heap;
int i = 0;
int res = w;
while(k--) {
while(i<n && res >= vecs[i].first)heap.push(vecs[i++].second);
if(heap.size()) {
res += heap.top();
heap.pop();
}
}
return res;
}
};