LeetCode-502.IPO -- 贪心

LeetCode502 - IPO – 贪心

题目链接

题目大意 :

给你做一些项目，每个项目有它的花费成本(运营资金)Capital，和利润Profits(一定要注意这个是纯利润，也就是说你做完这个项目之后，可以赚这么多钱，但是你的钱W必须要大于这个项目的Capital才能做)，现在只允许你做K个项目，并给你一笔启动资金W(你一开始有的钱)，要你从中选K个项目(或者因为钱不够做不了K个项目)，使得最后的钱最多(使W最大)，还有就是要注意每次是做一个项目，最多做K个项目。

---

解析 :

这个题目要用到贪心的思想，首先准备两个堆，一个按照花费成本升序的小根堆，另一个按照纯利润降序的大根堆。

• 首先我们将所有的项目加入到小根堆中，则这个堆中的项目是按照花费成本升序的。
• 然后，我们从小根堆中拿出所有能做的项目(目前的W(目前有的钱))放到按照利润降序的大根堆中。
• 然后我们从大根堆中取出堆顶元素，也就是说我们这一次做这个项目。
• 循环K次，做K个项目。
• 注意，当大根堆中没有元素，但是循环没有结束的时候，就可以返回了，因为现有的钱已经做不起任何的项目。

看题目中例子的过程

代码如下 :

import java.util.Comparator;
import java.util.PriorityQueue;


/**
 * LeetCode502-IPO
 * 题目链接 : https://leetcode.com/problems/ipo/description/
 */
public class 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; //按照c升序排列
        }
    }


    //大根堆
    public static class MaxProfitComparator implements Comparator<Node> {

        @Override
        public int compare(Node o1, Node o2) {
            return -(o1.p - o2.p); //按照p降序排列
        }
    }

    //最多做k个项目　　初始启动资金  利润数组　　花费数组
    public int findMaximizedCapital(int k, int W, int[] Profits, int[] Capital) {
        Node[] node = new Node[Profits.length];
        for (int i = 0; i < Profits.length; i++) {
            node[i] = new Node(Profits[i], Capital[i]);
        }
        PriorityQueue<Node> minCostQ = new PriorityQueue<Node>(new MinCostComparator());
        PriorityQueue<Node> maxProfitQ = new PriorityQueue<Node>(new MaxProfitComparator());
        for (int i = 0; i < node.length; i++) {
            minCostQ.add(node[i]);
        }
        //最多做k个项目
        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;
    }

    public static void main(String[] args) {
        int k = 2,W = 0;
        int[] Profits = {1,2,3};
        int[] Capital = {0,1,1};
        System.out.println(new IPO().findMaximizedCapital(k,W,Profits,Capital));
    }
}