C++ 中的 IPO
c++server side programmingprogramming更新于 2025/6/25 21:07:17
假设一家公司 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 := 利润规模
- 初始化 i := 0，当 i < 时n，更新(将 i 加 1)，执行 −
- 将 { Profits[i], Capital[i] } 插入 pqCapital
- for 初始化 i := 0，当 i
- while (pqCapital 非空且 pqCapital 顶部元素的第二个值 <= W)，执行 −
- 将 pqCapital 的顶部元素插入 pqMain
- 从 pqCapital 中删除元素
- 如果 pqMain 为空，则 −
- 退出循环
- W := W + 顶部元素的第一个值pqMain 的
- 从 pqMain 中删除元素
- while (pqCapital 非空且 pqCapital 顶部元素的第二个值 <= 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
