贪心之利润最高

package com.zhang.reflection.面试.算法模版.贪心算法;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 给你一个启动资金w，和一个最大项目次数k。
 * 然后，有两个数组，一个cost[]，里面记录了每个项目需要花费的资金。一个profit数组，里面记录了每个项目完成后可以获取的利润。
 * 然后请你计算出，给你一个初始资金w，
 * 和最大项目次数k的情况下，可以获取的最大利润。每次只能做一个项目，不能同时进行几个项目。
 * 例如：初始资金10，k=3，cost[10，20，30，40]，profit[10，20，30，40]
 * 那么，初始资金只能够花费来进行第一个10的项目，其他项目买不起，然后，第一个项目做完，利润是10，现在手里有20，
 * 就可以进行第二个项目了，然后再累加利润，看看能不能再解锁新项目。注意，每个项目只能做一次。
 */
public class 利润最多 {
    public static void main(String[] args) {
        int k=3;
        int[] cost=new int[]{10,20,30,40,50};
        int[] profit=new int[]{10,20,30,40,50};
        System.out.println( findMaxProfit(k,10,profit,cost));


    }
    public static int findMaxProfit(int k,int w,int[] profit,int[] cost){
        Node[] nodes=new Node[profit.length];
        for (int i = 0; i < profit.length; i++) {
            nodes[i]=new Node(profit[i],cost[i]);
        }
        PriorityQueue<Node> min=new PriorityQueue<>(new MinCostComparator());
        PriorityQueue<Node> max=new PriorityQueue<>(new MaxProfitComparator());
        for (int i = 0; i < nodes.length; i++) {
            min.add(nodes[i]);
        }
        for (int i = 0; i < k; i++) {
            while (!min.isEmpty()&&w>=min.peek().c){
                max.add(min.poll());
            }
            if(max.isEmpty()){
                return w;
            }
            w+=max.poll().p;
        }
        return w;
    }
}
class Node{
    public int p;
    public int c;
    public Node(int p,int c){
        this.p=p;
        this.c=c;
    }
}

class MinCostComparator implements Comparator<Node> {


    @Override
    public int compare(Node o1, Node o2) {
        return o1.c-o2.c;
    }
}

class MaxProfitComparator implements Comparator<Node>{

    @Override
    public int compare(Node o1, Node o2) {
        return o2.p-o1.p;
    }
}