假設(shè) 力扣（LeetCode）即將開始 IPO 。為了以更高的價格將股票賣給風(fēng)險投資公司，力扣 希望在 IPO 之前開展一些項目以增加其資本。 由于資源有限，它只能在 IPO 之前完成最多 k 個不同的項目愧旦。幫助 力扣 設(shè)計完成最多 k 個不同項目后得到最大總資本的方式。
給你 n 個項目定罢。對于每個項目 i 笤虫，它都有一個純利潤 profits[i] ，和啟動該項目需要的最小資本 capital[i] 祖凫。
最初琼蚯，你的資本為 w 。當(dāng)你完成一個項目時惠况，你將獲得純利潤遭庶，且利潤將被添加到你的總資本中。
總而言之稠屠，從給定項目中選擇 最多 k 個不同項目的列表峦睡，以 最大化最終資本 ，并輸出最終可獲得的最多資本权埠。
答案保證在 32 位有符號整數(shù)范圍內(nèi)榨了。
示例 1：
輸入：k = 2, w = 0, profits = [1,2,3], capital = [0,1,1] 輸出：4 解釋： 由于你的初始資本為 0，你僅可以從 0 號項目開始攘蔽。 在完成后龙屉，你將獲得 1 的利潤，你的總資本將變?yōu)?1满俗。 此時你可以選擇開始 1 號或 2 號項目转捕。 由于你最多可以選擇兩個項目作岖，所以你需要完成 2 號項目以獲得最大的資本。 因此五芝，輸出最后最大化的資本痘儡，為 0 + 1 + 3 = 4。
來源：力扣（LeetCode）
讀題
- 最多做 k 個不同項目
- 做項目不花錢枢步，只看自己的錢夠不夠成本谤辜。w >= capital[i]
要求：最大化的最終持有資本。
讀完題价捧，就一個感覺，要干就干最能掙錢的涡戳，這不是讓我貪心嗎结蟋？好家伙，沖沖沖...
解題思路
講個故事先
你是 LeetCode CEO渔彰，將要走向巔峰 IPO嵌屎，為了想拉高股票價格多（割）賺（韭）錢（cai），你要在限定項目次數(shù)內(nèi)盡可能的多掙錢恍涂。
你的初始資本為 w宝惰，做項目空手套白狼不花錢。需要注意的是你的資本 w 需要 >= 想干項目所需的成本再沧，這項目只能干一次尼夺。
- 首先，你只能干 k 個項目炒瘸。那肯定得每次干的項目都得最賺錢淤堵，這樣你的資本 w 就增長，持有資本越多就能干更大更賺錢的項目顷扩。
- 好拐邪，咱來干第一票，得選所有能干的項目中最賺錢的隘截，咋辦扎阶？ 先把項目按照所需資本從小到大 sort 一下。然后做最賺錢的那個項目婶芭。咱做了最賺錢的項目东臀，空手套白狼，不花錢犀农。同時呢啡邑，咱初始資產(chǎn) + 這第一票賺的錢，持有資本增長了井赌，那不得趕緊物色下一個最賺錢的谤逼。
- 之后操作就像這第一票一樣贵扰，直到干完 k 次。
- done流部，你本次臨時當(dāng) CEO 所持有的的最終最大資本就出來了戚绕。
回到代碼層面
- 上邊小故事里說了要把項目所需資金從小到大排序一下。
- 用一個優(yōu)先隊列
priority_queue<int> q枝冀，每次循環(huán)時候?qū)㈨椖克栀Y金小于所持資本 w 的項目利潤放入優(yōu)先隊列 q舞丛，自動排序。每次取 q 的 top()果漾，更新 w球切。然后如是這般循環(huán) k 次即可。
貪心其實就是像這樣每一個小階段局部最優(yōu)绒障，然后就可以推到全局最優(yōu)吨凑。就像這題每次干最賺錢的，最后就能得到最大持有資本户辱。
PS:
-
Q: C++ sort 對
vector<pair<int, int>>優(yōu)先比較 pair.first鸵钝，然后比較 pair.second ? -
A:
std::sort可以不寫比較函數(shù)，不寫排序函數(shù)的話就用operator<來比較庐镐。而std::pair::operator<按標(biāo)準(zhǔn)恩商，兩個 std::pair 的 first 為第一優(yōu)先級，second 為第二優(yōu)先級必逆。
template <class _Ty1, class _Ty2>
_NODISCARD constexpr bool operator<(const pair<_Ty1, _Ty2>& _Left, const pair<_Ty1, _Ty2>& _Right) {
return _Left.first < _Right.first || (!(_Right.first < _Left.first) && _Left.second < _Right.second);
}
代碼
class Solution {
public:
int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {
vector<pair<int, int>> info;
int size = profits.size();
for(int i = 0; i < size; i++) {
info.push_back({capital[i], profits[i]});
}
sort(info.begin(), info.end());
priority_queue<int> q;
int idx = 0, iSize = info.size();
while(k--){
while(idx < iSize && w >= info[idx].first) {
q.push(info[idx++].second);
}
if(q.empty()) {
break;
}else {
w += q.top();
q.pop();
}
}
return w;
}
};
補充&鳴謝
在此非常感謝代碼隨想錄怠堪。這位老哥的 leetcode 刷題筆記分類整理不同算法類型，也有不同語言版本名眉，對于菜雞的我來說幫助很大研叫。
另外，我也整了個刷題筆記璧针，堅持費曼學(xué)習(xí)法嚷炉，吃進去，產(chǎn)出來探橱。
如果感覺本題解對你有幫助申屹，請不要吝嗇點贊????啊 沖沖沖...
