【Leetcode】502.IPO（困难）

一、题目

1、题目描述

假设 力扣（LeetCode）即将开始 IPO 。为了以更高的价格将股票卖给风险投资公司，力扣 希望在 IPO 之前开展一些项目以增加其资本。 由于资源有限，它只能在 IPO 之前完成最多 k 个不同的项目。帮助 力扣 设计完成最多 k 个不同项目后得到最大总资本的方式。

给你 n 个项目。对于每个项目 i ，它都有一个纯利润 profits[i] ，和启动该项目需要的最小资本 capital[i] 。

最初，你的资本为 w 。当你完成一个项目时，你将获得纯利润，且利润将被添加到你的总资本中。

总而言之，从给定项目中选择 最多k 个不同项目的列表，以 最大化最终资本 ，并输出最终可获得的最多资本。

答案保证在 32 位有符号整数范围内。

示例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。

示例2：

输入：k = 3, w = 0, profits = [1,2,3], capital = [0,1,2]
输出：6

2、基础框架

class Solution {
    
public:
    int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {
    

    }
};

3、原题链接

502. IPO

二、解题报告

1、思路分析

（1）准备一个小根堆，将所有项目放入该堆中，用花费进行排序。
（2）准备一个大根堆，一开始为空，用 利润 进行排序。
（3）基于 $M$，弹出小根堆中能做的项目 $x$，放入大根堆中（按利润排序），弹出大根堆的堆顶项目，就做该项目，做完该项目后，$M=M+profits[x]$。重复该过程直到完成 $K$ 个项目。

总结来说，就是：

1. $M$ 去解锁小根堆中的项目，放入大根堆中；
2. 弹出大根堆顶部的项目，就做它；
3. 重复以上两个过程，直到做完 $K$ 个项目

2、时间复杂度

$O(n\times logn)$

3、代码详解

C++ 版：

class Solution {
    
public:

    class Program {
    
    public:
        int capital;
        int profit;
        
        Program(int c, int p) : capital(c), profit(p) {
    }
    };


    struct mincapitalCMP {
    
        bool operator()(Program* const &p1, Program* const &p2) const {
    
            return p1->capital > p2->capital; 
        }
    };

    struct maxProfitCMP {
    
        bool operator()(Program* const &p1, Program* const &p2) const {
    
            return p1->profit < p2->profit;
        } 
    };

    int findMaximizedCapital(int k, int w, vector<int> &profits, vector<int> &capitals) {
    
        priority_queue<Program*, vector<Program*>, mincapitalCMP> mincapitalQue;
        priority_queue<Program*, vector<Program*>, maxProfitCMP> maxProfitQue;

        //所有项目加入到最小花费的堆中
        for (int i = 0; i < profits.size(); i++) {
    
            mincapitalQue.push(new Program(capitals[i], profits[i]));
        }
        
        //能做的项目放到最大收益堆中 
        for (int i = 0; i < k; i++) {
    
            while (!mincapitalQue.empty() && mincapitalQue.top()->capital <= w) {
    
                maxProfitQue.push(mincapitalQue.top());
                mincapitalQue.pop();
            }

            //当用w做不了任何项目的时候，直接返回
            if (maxProfitQue.empty()) return w;

            w += maxProfitQue.top()->profit;
            maxProfitQue.pop();
        }

        return w;
    }

};

Java版：

public class Solution {
    

	// 最多K个项目
	// W是初始资金
	// Profits[] Capital[] 一定等长
	// 返回最终最大的资金
	public static int findMaximizedCapital(int K, int W, int[] Profits, int[] Capital) {
    
		PriorityQueue<Program> minCostQ = new PriorityQueue<>(new MinCostComparator());
		PriorityQueue<Program> maxProfitQ = new PriorityQueue<>(new MaxProfitComparator());
		for (int i = 0; i < Profits.length; i++) {
    
			minCostQ.add(new Program(Profits[i], Capital[i]));
		}
		for (int i = 0; i < K; i++) {
    
			while (!minCostQ.isEmpty() && minCostQ.peek().c <= W) {
    
				maxProfitQ.add(minCostQ.poll());
			}
            //当用W做不了任何项目的时候，就直接返回。
			if (maxProfitQ.isEmpty()) {
    
				return W;
			}
			W += maxProfitQ.poll().p;
		}
		return W;
	}

	public static class Program {
    
		public int p;
		public int c;

		public Program(int p, int c) {
    
			this.p = p;
			this.c = c;
		}
	}

	public static class MinCostComparator implements Comparator<Program> {
    

		@Override
		public int compare(Program o1, Program o2) {
    
			return o1.c - o2.c;
		}

	}

	public static class MaxProfitComparator implements Comparator<Program> {
    

		@Override
		public int compare(Program o1, Program o2) {
    
			return o2.p - o1.p;
		}

	}
}