自定义类型的小根堆(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;
}
};