天天看點

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

繼續閱讀