卡片式设计网站制作直播发布会

难度困难127收藏分享切换为英文接收动态反馈

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

package 优先队列;import java.util.Arrays;
import java.util.PriorityQueue;/** https://leetcode-cn.com/problems/ipo/* 解题思路* 1. 按所需要的资本排序* 2. 在小于等于总资本的项目启动资本中选择最大的利润项目* 3. 更新总资本w* 4.重复2和3的操作,直到选择k次* 解题方法* 1.小于等于总资本的项目压入堆中* 2.利用大根堆，每次取出最大利润，更新手中资本* 3. 重复1 2操作* 4. 如果当前的堆为空，则此时我们应当直接返回。*/
public class _502_IPO {public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
//    	定义一个数组指针int node=0;
//    		将项目利润和资本合并成二维数组int[][] res=new int [profits.length][2];for(int i=0;i<profits.length;i++) {res[i][0]=profits[i];res[i][1]=capital[i];}
//    		对二维数组进行排序，排序的依据是最小资本capitalArrays.sort(res,(a,b)->a[1]-b[1]);
//    	定义优先队列,从大到小排序输入进来的利润PriorityQueue<Integer> queue=new PriorityQueue<>((x,y)->y-x);//大顶堆//		如果到达指定的k个项目就停止while(k-->0) {
//			通过循环将符合条件的资本入队while(node<profits.length&& res[node][1]<=w) {queue.add(res[node][0]);node++;}
//			如果队列为空，就出队利润加入到总资产里if (!queue.isEmpty()) {w=w+queue.poll();}else {
//				如果队列为空说明没有符合资本的项目了break;}}return w;}
}

本人csdn博客：https://blog.csdn.net/weixin_46654114

转载说明：跟我说明，务必注明来源，附带本人博客连接。