leetcode 502.IPO

思路：贪心+优先队列

贪心算法体现在局部最优，对这个题，我们可以这样想：

首先我们需要得到最大资本，有两个因素限制我们：第一个，就是成本问题，成本不够，我们就无法选择好的项目；第二个，就是项目所能收获的利润问题。

这两个因素我们应该优先先考虑成本问题，然后再考虑收益利润问题。

另外，我们看到题目中有提到，最多的k个项目。这应该很明显，我们可以用堆的思想去存储数据。那么，堆中的优先级谁最高呢？当然是成本低并且收获利润高的好了。但这也会导致一个问题，就是当我们选择了成本低利润一般的项目，但是我们有时候成本够了却没有拿到高利润的项目，这样用这样的优先级就不好了。举例：本身你有0资本，（前者的数字是成本，后者为利润）这么几个项目（0，2）（1，2）（2，4）如果照上面说的去做，我们选择了第一个项目之后，就会首先选择第二个项目而不是第三个项目了。这样就导致利润不能最大化。

那么我们怎么办呢？其实倒过来想，我们就让利润收获大的放优先级最高的，先不用考虑成本问题。我们就按照利润收获大的为优先级高的规则入堆，然后我们去取堆中的元素。

当前我们取到的是这几个项目中利润最高的，所以这个时候我们只需要考虑成本了。成本不够，我们就出堆，暂时放到一个队列当中（因为我们后期资本够了反而可以用这个出堆的项目）；成本够，我们就用，然后让刚刚已经出堆的项目再回来，我们下一次取的时候再把他们考虑进去就行了。OK，这样就行了，一直到我们取够k个项目为止。

class Solution {
    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        PriorityQueue<int[]>q=new PriorityQueue<>((a,b)->b[1]-a[1]);
        for(int i=0;i<profits.length;i++){
            q.add(new int[]{capital[i],profits[i]});
        }
        int cnt=0;
        Deque<int[]>pq=new LinkedList<>();
        while(!q.isEmpty()&&cnt<k){
            if(w<q.peek()[0]){
                pq.addLast(q.poll());
            }
            else{
                w+=q.poll()[1];
                while(!pq.isEmpty()){
                    q.add(pq.removeFirst());
                }
                cnt++;
            }
        }
        return w;
    }
}