数据结构
网络
关系型数据库管理系统
操作系统
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 次查看
广告