LeetCode刷题【502】IPO

假设 力扣（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

提示：

• 1 <= k <= 105
• 0 <= w <= 109
• n == profits.length
• n == capital.length
• 1 <= n <= 105
• 0 <= profits[i] <= 104
• 0 <= capital[i] <= 109

题解

从题面来理解，第一步，从所有项目中找到本金小于等于当前拥有的总的本金的项目，这些项目为可投资项目。第二步，由于给出的是纯利润，且题面并没有要求说本金最大化优化使用，那么就可以最简单的直接选利润最大的一个项目来投，等利润拿到了，再去投资下一个项目。

而如果要求本金最大化优化使用的话，可能要考虑一次投资多个项目，什么样的项目组合能得到最大化利润，这样的要求就更加复杂话了，而实际的企业投资操作比这个更加复杂，更多的风险控制，不是什么能套个公式算算能到结论的。

好的，既然上面思路理出来了，我们知道提供出来的profits和capital是索引对应关系，所以第一步的操作中，可以维护一个堆，堆的内容和capital的索引和本金的值，这样取的时候从顶部取出所有小于当前拥有的本金的值。

接下来第二步，前面我们已经拿到了所有的符合投资要求的索引了，所以这里，我们对应的也建一个堆，按照profits利润值降序排列。然后从顶部取出一个，算出新的总的本金金额。

到这里编码思路就已经出来了。

class Solution {
    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int amount = w;
        //堆1成本降序
        //内部结构[0:索引，1:成本]
        //堆1中目前成本越小的越排在前面，便于下一步寻找符合成本要求的项目
        PriorityQueue<int[]> queue1 = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1]-o2[1];
            }
        });
        for (int i = 0; i < capital.length; i++) {
            queue1.offer(new int[]{i,capital[i]});
        }

        //queue2
        //int[0] 成本  int[1]利润  利润越大的越在前面
        PriorityQueue<int[]> queue2 = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o2[1]-o1[1];
            }
        });

        while (k>0){
            while (!queue1.isEmpty() && queue1.peek()[1] <= amount){
                //arr[0]索引位，arr[1]是成本位
                int[] arr = queue1.poll();
                queue2.offer(new int[]{arr[1],profits[arr[0]]});
            }
            if (queue2.isEmpty()){
                //没有能投的项目了，钱.......不够
                break;
            }
            int[] arr2 = queue2.poll();
            k--;
            //赚了 arr2[1]
            amount +=arr2[1];
        }
        return amount;
    }
}

那么，你学废了嘛！~