import java.util.Comparator;
import java.util.PriorityQueue;public class test32 {//输入正数数组costs、正数数组profits、正数K、正数M//costs[i]表示i号项目花费,profits[i]表示i号项目在扣除花费后还挣的钱//K表示有多少项目//M表示初始资金//每做完一个项目,获得的收益可以支持做下一个项目。不能并行的做项目//输出最后获得的最大钱数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>{public int compare(Program o1 , Program o2){return o1.c - o2.c;}}//根据利润建立大根堆的比较器public static class MaxProfitComparator implements Comparator<Program>{public int compare(Program o1 ,Program o2){return o2.p - o1.p;}}//costs[i]表示i号项目花费,profits[i]表示i号项目在扣除花费后还挣的钱//K表示有多少项目//M表示初始资金public static int fingMaximizedCapital(int K ,int M ,int[] Profits , int[] costs){//建出花费的小根堆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] , costs[i]));}for (int i = 0; i < K; i++) {//如果小根堆不为空且小根堆堆顶的花费小于目前的资金数, 小根堆弹出的项目进入大根堆//即目前所有可以做的项目全进大根堆来比较利润while (!minCostQ.isEmpty() && minCostQ.peek().c <= M){maxProfitQ.add(minCostQ.poll());}//当大根堆空了,就不做项目,提前返回Mif(maxProfitQ.isEmpty()){return M;}//大根堆的堆顶的利润加到M中M += maxProfitQ.poll().p;}return M;}
}