leetcode 502. IPO k个项目利益最大化 + 典型的贪心算法

布满荆棘的人生 2022-06-03 03:06 136阅读 0赞

Suppose LeetCode will start its IPO soon. In order to sell a good price of its shares to Venture Capital, LeetCode would like to work on some projects to increase its capital before the IPO. Since it has limited resources, it can only finish at most k distinct projects before the IPO. Help LeetCode design the best way to maximize its total capital after finishing at most k distinct projects.

You are given several projects. For each project i, it has a pure profit Pi and a minimum capital of Ci is needed to start the corresponding project. Initially, you have W capital. When you finish a project, you will obtain its pure profit and the profit will be added to your total capital.

To sum up, pick a list of at most k distinct projects from given projects to maximize your final capital, and output your final maximized capital.

Example 1:  
Input: k=2, W=0, Profits=\[1,2,3\], Capital=\[0,1,1\].

Output: 4

Explanation: Since your initial capital is 0, you can only start the project indexed 0.  
After finishing it you will obtain profit 1 and your capital becomes 1.  
With capital 1, you can either start the project indexed 1 or the project indexed 2.  
Since you can choose at most 2 projects, you need to finish the project indexed 2 to get the maximum capital.  
Therefore, output the final maximized capital, which is 0 + 1 + 3 = 4.  
Note:  
You may assume all numbers in the input are non-negative integers.  
The length of Profits array and Capital array will not exceed 50,000.  
The answer is guaranteed to fit in a 32-bit signed integer.

题意很简单，就是利益最大化，是一个典型的贪心算法

这道题说初始时我们的资本为0，可以交易k次，并且给了我们提供了交易所需的资本和所能获得的利润，让我们求怎样选择k次交易，使我们最终的资本最大。虽然题目中给我们的资本数组是有序的，但是OJ里的test case肯定不都是有序的，还有就是不一定需要资本大的交易利润就多，该遍历的时候还得遍历。我们可以用贪婪算法来解，每一次都选择资本范围内最大利润的进行交易，那么我们首先应该建立资本和利润对，然后根据资本的大小进行排序，然后我们根据自己当前的资本，用二分搜索法在有序数组中找第一个大于当前资本的交易的位置，然后往前退一步就是最后一个不大于当前资本的交易，然后向前遍历，找到利润最大的那个的进行交易，把利润加入资本W中，然后将这个交易对删除，这样我们就可以保证在进行k次交易后，我们的总资本最大，

建议和这个文章一起学习[\[LeetCode\] IPO 上市][LeetCode_ IPO]

代码如下：

这里的二分查找是寻找第一个比W大的元素，所以要这么做

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    
    using namespace std;
    
    
    class Solution
    {
    public:
        int findMaximizedCapital(int k, int W, vector<int>& profits, vector<int>& capital) 
        {
            vector<pair<int, int>> v;
            for (int i = 0; i < capital.size(); i++)
                v.push_back(make_pair(capital[i], profits[i]));
    
            sort(v.begin(), v.end());
            for (int i = 0; i < k; i++)
            {
                if (v.size() == 0)
                    break;
                int left = 0, right = v.size();
                while (left < right)
                {
                    int mid = (right - left) / 2 + left;
                    if (v[mid].first <= W)
                        left = mid+1;
                    else
                        right = mid;
                }
    
                int maxP = 0 , index = 0;
                for (int j = left-1; j >= 0; j--)
                {
                    if (v[j].first <= W && v[j].second > maxP)
                    {
                        maxP = v[j].second;
                        index = j;
                    }
                }
                W = W + maxP;
                v.erase(v.begin() + index);
            }
            return W;
        }
    };

这个方法可能超时，所以使用容器最好，

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    
    using namespace std;
    
    
    class Solution {
    public:
        int findMaximizedCapital(int k, int W, vector<int>& Profits, vector<int>& Capital) {
            priority_queue<int> q;
            multiset<pair<int, int>> s;
            for (int i = 0; i < Capital.size(); ++i) 
            {
                s.insert({ Capital[i], Profits[i] });
            }
            for (int i = 0; i < k; ++i) {
                for (auto it = s.begin(); it != s.end(); ++it) 
                {
                    if (it->first > W)
                        break;
                    q.push(it->second);
                    s.erase(it);
                }
                if (q.empty())
                    break;
                W += q.top();
                q.pop();
            }
            return W;
        }
    };

[LeetCode_ IPO]: https://www.cnblogs.com/grandyang/p/6788811.html?utm_source=itdadao&utm_medium=referral