推 Rushia: 大師 02/23 09:12
這一篇大概有50篇JPTT廢文價值左右==
502. IPO
有資本w，有n個產品，選第i個產品做可以得到其利益profit[i](每個產品只能做一次)，
有前提是選做第i個產品時本金w必須 >= capital[i]，若做了則可使資本增加profit[i]，
問最多做k個產品可以得到的最大資本
n <= 1e5, profit[i] <= 1e4, capital[i] <= 1e9, w <= 1e9, k <= 1e5.
答案在32bit整數以內
然後就想到把profit[i]對capital[i]排序一下，然後把 capital[i] <= w 對應的
profit[i]丟進大根堆...
C++ code:
class Solution {
public:
int findMaximizedCapital(int k, int w, vector<int>& p, vector<int>& c) {
int n = p.size();
vector<pair<int, int>> v;
for(int i=0; i<n; i++) v.push_back({c[i], p[i]});
sort(v.begin(), v.end());
priority_queue<int> q;
int cur = 0;
while(k){
while(cur < n && w >= v[cur].first){
q.push(v[cur].second);
cur++;
}
if(q.empty()) break;
w += q.top();
q.pop();
k--;
}
return w;
}
};
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.3.144.80 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1677112895.A.31A.html