資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中的 IPO
假設一家公司 A 很快就要開始其 IPO。為了以一個好價格將其股票出售給 B，A 希望在 IPO 之前開展一些專案來增加其資本。A 的資源有限，在 IPO 之前最多隻能完成 k 個不同的專案。你能幫助 A 設計最佳方案，以在完成最多 k 個不同專案後最大化其總資本嗎？
假設我們有幾個專案。對於每個專案 i，它都有一個純利潤 Pi，並且需要一個最小資本 Ci 來啟動相應的專案。首先，我們有 W 資本。當我們完成一個專案時，我們將獲得其純利潤，並且該利潤將加到我們的總資本中。
總而言之，從給定的專案列表中選擇最多 k 個不同的專案列表，以最大化我們的最終資本，並輸出最終最大化的資本。
因此，如果輸入類似於 - k = 2，W = 0，利潤列表類似於 [1,2,4]，資本為 [0,1,1]，則輸出將為 5。這是因為，由於我們最初擁有 0 的資本，因此我們可以啟動索引為 0 的專案，因此我們可以獲得 1 的利潤，因此資本將為 1。擁有 1 的資本，我們可以啟動索引為 1 或 2 的專案，我們將選擇索引為 2 的專案以獲得更多利潤，因此最終答案將為 0 + 1 + 4 = 5。
為了解決這個問題，我們將遵循以下步驟 -
- 建立優先順序佇列 pqCapital 和 pqMain
- n := Profits 的大小
- 初始化 i := 0，當 i < n 時，更新（i 增加 1），執行 -
- 將 { Profits[i], Capital[i] } 插入 pqCapital
- 初始化 i := 0，當 i <k 時，更新（i 增加 1），執行 -
- 當 (pqCapital 不為空且 pqCapital 頂部元素的第二個值 <= W) 時，執行 -
- 將 pqCapital 的頂部元素插入 pqMain
- 從 pqCapital 刪除元素
- 如果 pqMain 為空，則 -
- 退出迴圈
- W := W + pqMain 頂部元素的第一個值
- 從 pqMain 刪除元素
- 當 (pqCapital 不為空且 pqCapital 頂部元素的第二個值 <= W) 時，執行 -
- 返回 W
讓我們看看以下實現以更好地理解 -
示例
#include <bits/stdc++.h>
using namespace std;
struct Comparator{
bool operator() (pair <int, int> a, pair <int, int> b){
return !(a.second < b.second);
}
};
class Solution {
public:
int findMaximizedCapital(int k, int W, vector<int>& Profits, vector<int>& Capital) {
priority_queue < pair <int, int>, vector < pair <int, int> >, Comparator> pqCapital;
priority_queue < pair <int ,int> > pqMain;
int n = Profits.size();
for(int i = 0; i < n; i++){
pqCapital.push({Profits[i], Capital[i]});
}
for(int i = 0; i < k; i++){
while(!pqCapital.empty() && pqCapital.top().second <= W){
pqMain.push(pqCapital.top());
pqCapital.pop();
}
if(pqMain.empty()) break;
W += pqMain.top().first;
pqMain.pop();
}
return W;
}
};
main(){
Solution ob;
vector<int> v = {1,2,4}, v1 = {0,1,1};
cout << (ob.findMaximizedCapital(2,0, v, v1));
}輸入
2 0 [1,2,4] [0,1,1]
輸出
5
更新於: 2020 年 6 月 1 日
320 次檢視
廣告