自定義類型的小根堆(priority_queue)
struct Node{
int cost;
int profit;
};
struct cmp1{
bool operator()(Node n1,Node n2) {
return n1.profit < n2.profit;//大根堆
}
};
struct cmp2{
bool operator()(Node n1,Node n2) const{
return n1.cost > n2.cost;//小根堆
}
};
class Solution {
public:
/**
* 代碼中的類名、方法名、參數名已經指定,請勿修改,直接傳回方法規定的值即可
*
*
* @param k int整型 表示你隻能串行的最多做k個項目
* @param m int整型 表示你初始的資金
* @param costs int整型vector costs[i]表示i号項目的花費
* @param profits int整型vector profits[i]表示i号項目在扣除花費之後還能掙到的錢(利潤)
* @return int整型
*/
int findMaximizedCapital(int k, int m, vector<int>& costs, vector<int>& profits) {
// write code here
vector<vector<int> >val;
for(int i=0;i<costs.size();++i){
val.push_back({costs[i],profits[i]});
}
priority_queue<Node,vector<Node>,cmp2 >min;//小頂堆--cost
priority_queue<Node,vector<Node>,cmp1 >max;//大頂堆----profit
for(int i=0;i<costs.size();++i){
struct Node node;
node.cost=costs[i];
node.profit=profits[i];
min.push(node);
}
for(int i=1;i<=k;++i){
while(!min.empty()){
if(min.top().cost<=m){
max.push(min.top());
min.pop();
}
else break;
}
if(max.empty())break;
m+=max.top().profit;
max.pop();
}
return m;
}
};