LeetCode:IPO

502. IPO

给定若干个项目。对于每个项目 i，它都有一个纯利润 P_i，并且需要最小的资本 C_i 来启动相应的项目。最初，你有 W 资本。当你完成一个项目时，你将获得纯利润，且利润将被添加到你的总资本中。
总而言之，从给定项目中选择最多 k 个不同项目的列表，以最大化最终资本，并输出最终可获得的最多资本。
示例 1:
输入: k=2, W=0, Profits=[1,2,3], Capital=[0,1,1].
输出: 4
解释:
由于你的初始资本为 0，你尽可以从 0 号项目开始。
在完成后，你将获得 1 的利润，你的总资本将变为 1。
此时你可以选择开始 1 号或 2 号项目。
由于你最多可以选择两个项目，所以你需要完成 2 号项目以获得最大的资本。
因此，输出最后最大化的资本，为 0 + 1 + 3 = 4。

思路：

肯定利润最高最赚钱。那么只需要做利润最高的即可，但是可能要投入的资本比本金多，这时候是不能做该项目的。因此可以建立一个项目花费的小顶堆，一开始把所有项目都加进去。然后比较小顶堆堆顶和本金，如果堆顶小于本金，则该项目可以做，把该项目放到项目利润大顶堆。弹出大顶堆堆顶，也就是做该项目，这时本金增多了，再次添加小顶堆中能做的项目。

class Solution {
public:
    struct node //构建项目
    {
        int pro;
        int cap;
        node(int a,int b):pro(a),cap(b){}
    };
    struct mincap  //重写仿函数，构建小顶堆
    {
        bool operator() (node n1,node n2) //函数要用{}
        {
            return n1.cap>n2.cap;
        }
    };
    struct maxpro  //重写仿函数，构建大顶堆
    {
        bool operator() (node n1,node n2)
        {
            return n1.pro<n2.pro;
        }
    };
    int findMaximizedCapital(int k, int W, vector<int>& Profits, vector<int>& Capital) {
        priority_queue<node,vector<node>,maxpro> maxprofits; //构建大顶堆
        priority_queue<node,vector<node>,mincap> mincaptial; //构建小顶堆
        for(int i=0;i<Profits.size();++i)
        {
            mincaptial.push({Profits[i],Capital[i]}); //将项目加入小顶堆
        }
        for(int i=0;i<k;++i)
        {
            while(!mincaptial.empty()&&mincaptial.top().cap<=W) //把可做的项目加到大顶堆
            {
                maxprofits.push(mincaptial.top());
                mincaptial.pop();
            }
            if(maxprofits.empty()) //大顶堆为空，说明项目均不可以做，即项目花费全部大于本金
                return W;
            W+=maxprofits.top().pro;//更新本金
            maxprofits.pop(); //弹出已做项目
        }
        return W;
    }
};

小知识：

1. 优先级队列(priority_queue)是一种先进，最高优先级先出，是采用堆结构实现的。
2. 定义：priority_queue<Type, Container, Functional>
3. Type是数据类型，可以使用系统内置类型，也可以使用自定义类型
4. Container是容器类型（Container必须是用数组实现的容器，比如vector,deque等等，但不能用 list。STL里面默认用的是vector）
5. Functional是比较的方式，可以自定义比较函数
6. 当需要用自定义的数据类型时才需要传入这三个参数，使用基本数据类型时，只需要传入数据类型，默认是大顶堆。

举几个例子

priority_queue<int, vector<int>, greater<int>> c; //小顶堆
priority_queue<pair<int,int>> //pair算做基本类型
priority_queue<T, vector<T>, compare> //自定义类型和比较方式

struct compare //自定义比较函数
{     
bool operator() (T a, T b)  //T类型的元素，x为其数据成员，用于定义比较方式
     {
        return a.x < b.x; //大顶堆
     }
 };  //末尾的分号不能丢