题目
输入:正数数组costs、正数数组profits、正数K、正数M。
costs[i]表示i号项目的花费，
profits[i]表示i号项目在扣除花费之后还能挣到的钱(利润)，
K表示你只能串行的最多做k个项目，
M表示你初始的资金。
说明:每做完一个项目，马上获得的收益，可以支持你去做下一个项目。不能并行的做项目。
输出:你最后获得的最大钱数。
这个题十分贴近人类的自然智慧，就好比在游戏中打怪升级。准备一个按项目花费组织的小根堆，将所有项目放入这个小根堆中；再准备一个按项目利润组织的大根堆。然后弹出所有小根堆中能够被初始资金W覆盖的项目，并放入大根堆中。获得大根堆堆顶项目的利润后，重复上面操作。
堆的知识可以参考这篇文章——比较器，，
package com.harrison.class09; import java.util.Comparator; import java.util.PriorityQueue; public class Code05_IPO { public static class Program{ public int profit; public int cost; public Program(int p,int c) { profit=p; cost=c; } } // 根据花费组织的小根堆 public static class minCostComparator implements Comparator<Program>{ public int compare(Program o1,Program o2) { return o1.cost-o2.cost; } } // 根据利润组织的大根堆 public static class maxProfitComparator implements Comparator<Program>{ public int compare(Program o1,Program o2) { return o2.profit-o1.profit; } } public static int findMaximizedCaptial(int K,int W,int[] Cost,int[] Profits) { PriorityQueue<Program> minCostQ=new PriorityQueue<>(new minCostComparator()); PriorityQueue<Program> maxProfitQ=new PriorityQueue<>(new maxProfitComparator()); for(int i=0; i<Cost.length; i++) { minCostQ.add(new Program(Profits[i], Cost[i])); } for(int i=0; i<K; i++) { while(!minCostQ.isEmpty() && W>=minCostQ.peek().cost) { maxProfitQ.add(minCostQ.poll()); } if(maxProfitQ.isEmpty()) {// 初始资金不够做完K个项目 || 总的项目个数不够K个 return W; } W+=maxProfitQ.poll().profit; } return W; } }
