LeetCode502.ipo

小灰灰 2022-04-24 06:32 153阅读 0赞

# 题目 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzA5MzUwMQ_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzA5MzUwMQ_size_16_color_FFFFFF_t_70 1]

# 思路 #

*  构建实体类（项目类）：  
    　属性：成本、（纯）利润
 *  创建大根堆和小根堆（使用优先队列和比较器）

1.  根据成本，将所有项目放入小根堆，（这样每次取出的就是成本最低的项目）。
2.  项目成本不超过资金，根据利润，取出的项目放入大根堆，（这样每次取出的就是利润最大的项目）。
3.  当项目数量大于k个，大根堆中无项目，结束。

# 代码 #

public class Code_03_IPO { 
    	public static class Node { 
    		public int p;
    		public int c;
    
    		public Node(int p, int c) { 
    			this.p = p;
    			this.c = c;
    		}
    	}
    
    	public static class MinCostComparator implements Comparator<Node> { 
    
    		@Override
    		public int compare(Node o1, Node o2) { 
    			return o1.c - o2.c;
    		}
    
    	}
    
    	public static class MaxProfitComparator implements Comparator<Node> { 
    
    		@Override
    		public int compare(Node o1, Node o2) { 
    			return o2.p - o1.p;
    		}
    
    	}
    
    	public static int findMaximizedCapital(int k, int W, int[] Profits, int[] Capital) { 
    		Node[] nodes = new Node[Profits.length];
    		for (int i = 0; i < Profits.length; i++) { 
    			nodes[i] = new Node(Profits[i], Capital[i]);
    		}
    
    		PriorityQueue<Node> minCostQ = new PriorityQueue<>(new MinCostComparator());
    		PriorityQueue<Node> maxProfitQ = new PriorityQueue<>(new MaxProfitComparator());
    		for (int i = 0; i < nodes.length; i++) { 
    			minCostQ.add(nodes[i]);
    		}
    		for (int i = 0; i < k; i++) { 
    			while (!minCostQ.isEmpty() && minCostQ.peek().c <= W) { 
    				maxProfitQ.add(minCostQ.poll());
    			}
    			if (maxProfitQ.isEmpty()) { 
    				return W;
    			}
    			W += maxProfitQ.poll().p;
    		}
    		return W;
    	}
    
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzA5MzUwMQ_size_16_color_FFFFFF_t_70]: /images/20220218/e16b1c2b2c67457ca582055f1f65408d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzA5MzUwMQ_size_16_color_FFFFFF_t_70 1]: /images/20220218/e6e17abedea948e6a53786218bfb4fc7.png