天天看点

自定义类型的小根堆(priority_queue)

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

继续阅读