package com.jiucaiyuan.net.question;



import java.util.Comparator;

import java.util.PriorityQueue;



/**

 * 【问题】做一个项目，有成本，也有利润，一堆项目，如何选择做，实现收益最大？

 * 【思路】把所有项目，按照成本放入小根堆，从小根堆中拿出可以做的项目，然后按照利润放入大跟堆，开始先做大根堆的对顶项目

 *

 * @Author jiucaiyuan  2022/4/18 23:10

 * @mail services@jiucaiyuan.net

 */

public class MaxProfits {

    public static class Node {

        public int cost;

        public int profit;



        public Node(int cost, int profit) {

            this.cost = cost;

            this.profit = profit;

        }

    }



    public static class MinCostComparator implements Comparator<Node> {

        @Override

        public int compare(Node node1, Node node2) {

            return node1.cost - node2.cost;

        }

    }



    public static class MaxProfitComparator implements Comparator<Node> {

        @Override

        public int compare(Node node1, Node node2) {

            return node2.profit - node1.profit;

        }

    }



    /**

     * 没做完一个项目，马上获得收益，可以支持继续做下一个项目，输出最后获得的最大钱数

     *

     * @param k       只能串行，最多做k个项目

     * @param w       初始资金

     * @param profits profits[i]是i号项目扣除成本后还能剩下的钱（利润）

     * @param costs   costs[i]是i号项目的花费

     * @return

     */

    public static int findMaximizedCapital(int k, int w, int[] profits, int[] costs) {

        PriorityQueue<Node> minCostQueue = new PriorityQueue<>(new MinCostComparator());

        PriorityQueue<Node> maxProfitQueue = new PriorityQueue<>(new MaxProfitComparator());

        //所有项目扔到锁定池中，按照花费组织的小根堆

        for (int i = 0; i < profits.length; i++) {

            minCostQueue.add(new Node(costs[i], profits[i]));

        }

        for (int i = 0; i < k; i++) {  //进行k轮

            //能力所及的项目，全部解锁

            while (!minCostQueue.isEmpty() && minCostQueue.peek().cost < w) {

                maxProfitQueue.add(minCostQueue.poll());

            }

            if (maxProfitQueue.isEmpty()) {

                return w;

            }

            w += maxProfitQueue.poll().profit;

        }

        return w;

    }



    public static void main(String[] args) {

        int[] profits = {1, 2, 3, 5, 3, 2, 1, 4, 54, 5};

        int[] costs = {1, 1, 1, 1, 1, 12, 2, 1, 2, 1};

        System.out.println(findMaximizedCapital(10, 5, profits, costs));

    }

}