Re: [閒聊] 每日leetcode

[oin1104 (是oin的說)]

題目 :

You are given n projects where the ith project has a pure profit profits[i] and
a minimum capital of capital[i] is needed to start it.

Initially, you have w capital. When you finish a project, you will obtain its pu
re profit and the profit will be added to your total capital.

Pick a list of at most k distinct projects from given projects to maximize your
final capital, and return the final maximized capital.

叫你在k個東西以內賺錢
給你初始錢錢w 跟一堆項目
項目都有最低成本跟獲利
問你最多能賺多少錢



思路 :

因為每次都要最大或最小什麼的
所以用成priority queue就很好抓要的資料

首先 每次更新完w之後可以做的項目
都丟進去可以做的項目

然後從可以做的項目拿一個最多錢的

做k次

然後就姆咪


```cpp
class Solution {
public:
    int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& ca
pital)
    {
        int n = profits.size();
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,in
t>> > cappro;
        priority_queue<int , vector<int> , less<int> > pro;

        int wnow = w;

        for(int i = 0 ; i < n ; i ++)
        {
            cappro.push({capital[i] , profits[i]});
        }

        for(int i = 0 ; i < k ; i ++)
        {
            while(!cappro.empty() && cappro.top().first <= wnow)
            {
                //cout << cappro.top().first << " " << cappro.top().second << en
dl;
                pro.push(cappro.top().second);
                cappro.pop();
            }

            if(pro.empty())break;

            wnow += pro.top();
            pro.pop();
        }

        return wnow;

    }
};
```







--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.162.32.89 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1718424736.A.A30.html