502. IPO
给定若干个项目。对于每个项目 i，它都有一个纯利润 Pi，并且需要最小的资本 Ci 来启动相应的项目。最初，你有 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;
}
};
小知识：
- 优先级队列(priority_queue)是一种先进，最高优先级先出，是采用堆结构实现的。
- 定义：priority_queue<Type, Container, Functional>
- Type是数据类型，可以使用系统内置类型，也可以使用自定义类型
- Container是容器类型（Container必须是用数组实现的容器，比如vector,deque等等，但不能用 list。STL里面默认用的是vector）
- Functional是比较的方式，可以自定义比较函数
- 当需要用自定义的数据类型时才需要传入这三个参数，使用基本数据类型时，只需要传入数据类型，默认是大顶堆。
举几个例子
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; //大顶堆
}
}; //末尾的分号不能丢
