[leetcode] 502.ipo (difficult)

One 、 subject

1、 Title Description

hypothesis Power button （LeetCode） begin in a minute IPO . In order to sell shares to venture capital companies at a higher price , Power button Hope that in IPO Some projects have been carried out to increase its capital . Due to limited resources , It can only be found in IPO Most completed before k Different projects . help Power button Design completed at most k How to get the maximum total capital after different projects .

Here you are. n A project . For each project i , It has a net profit profits[i] , And the minimum capital required to start the project capital[i] .

first , Your capital is w . When you finish a project , You will get a net profit , And profits will be added to your total capital .

To make a long story short , Select... From a given project most k List of different items , With Maximize final capital , And export the most capital available .

The answer is guaranteed in 32 Bit signed integer range .

Example 1：

 Input ：k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]
 Output ：4
 explain ：
 Because your initial capital is  0, You can only from  0  Project start .
 After completion , You will receive  1  The profits of the , Your total capital will become  1.
 Now you can choose to start  1  Number or  2  Item No. .
 Because you can choose up to two items , So you need to finish  2  Project to maximize capital .
 therefore , Export the ultimate maximized capital , by  0 + 1 + 3 = 4.

Example 2：

 Input ：k = 3, w = 0, profits = [1,2,3], capital = [0,1,2]
 Output ：6

2、 Basic framework

class Solution {
    
public:
    int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {
    

    }
};

3、 Original link

502. IPO

Two 、 Problem solving report

1、 Thought analysis

（1） Prepare a small root pile , Put all items in this heap , use cost Sort .
（2） Prepare a large root pile , It's empty at first , use profits Sort .
（3） be based on $M$, Pop up the items that can be done in the small root pile $x$, Put it into the big root pile （ Sort by profit ）, Pop up the top item of the big root pile , Just do the project , After finishing the project ,$M=M+profits[x]$. Repeat the process until complete $K$ A project .

In conclusion , Namely ：

1. $M$ Go to unlock the items in the small root heap , Put it into the big root pile ;
2. Pop up the item at the top of the big root heap , Just do it ;
3. Repeat the above two processes , Until it's done $K$ A project

2、 Time complexity

$O(n\times logn)$

3、 Code details

C++ edition ：

class Solution {
    
public:

    class Program {
    
    public:
        int capital;
        int profit;
        
        Program(int c, int p) : capital(c), profit(p) {
    }
    };


    struct mincapitalCMP {
    
        bool operator()(Program* const &p1, Program* const &p2) const {
    
            return p1->capital > p2->capital; 
        }
    };

    struct maxProfitCMP {
    
        bool operator()(Program* const &p1, Program* const &p2) const {
    
            return p1->profit < p2->profit;
        } 
    };

    int findMaximizedCapital(int k, int w, vector<int> &profits, vector<int> &capitals) {
    
        priority_queue<Program*, vector<Program*>, mincapitalCMP> mincapitalQue;
        priority_queue<Program*, vector<Program*>, maxProfitCMP> maxProfitQue;

        // All items are added to the minimum cost heap 
        for (int i = 0; i < profits.size(); i++) {
    
            mincapitalQue.push(new Program(capitals[i], profits[i]));
        }
        
        // The projects that can be done are put into the maximum income pile  
        for (int i = 0; i < k; i++) {
    
            while (!mincapitalQue.empty() && mincapitalQue.top()->capital <= w) {
    
                maxProfitQue.push(mincapitalQue.top());
                mincapitalQue.pop();
            }

            // When used w When you can't do any projects , Go straight back to 
            if (maxProfitQue.empty()) return w;

            w += maxProfitQue.top()->profit;
            maxProfitQue.pop();
        }

        return w;
    }

};

Java edition ：

public class Solution {
    

	//  most K A project 
	// W It's the initial capital 
	// Profits[] Capital[]  It must be the same length 
	//  Return the final maximum funds 
	public static int findMaximizedCapital(int K, int W, int[] Profits, int[] Capital) {
    
		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], Capital[i]));
		}
		for (int i = 0; i < K; i++) {
    
			while (!minCostQ.isEmpty() && minCostQ.peek().c <= W) {
    
				maxProfitQ.add(minCostQ.poll());
			}
            // When used W When you can't do any projects , Go straight back .
			if (maxProfitQ.isEmpty()) {
    
				return W;
			}
			W += maxProfitQ.poll().p;
		}
		return W;
	}

	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> {
    

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

	}

	public static class MaxProfitComparator implements Comparator<Program> {
    

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

	}
}