题目描述 小埋创建的公司即将开始IPO。为了更高的将价格将股票卖给风险投资公司,小埋希望在 IPO 之前公司开展一些项目增加自己的公司资本。由于资源有限,它只能在 IPO 之前完成最多 K 个不同的项目。请帮助小埋设计完成最多 K个不同的项目后得到的最大总资本的方式。
小埋有这样 n 个项目。对于每个项目 i ,它都有一个纯利润 Ai ,和启动该项目需要的最小资本 Bi .
最初,小埋的资本为 w。当你完成一个项目时,你将获得纯利润,且利润将被添加到你的总资本当中。
总而言之,从这 n 个项目当中选择最多 K 个不同的项目列表,以最大化最终的资本,并输出最终可获得的最多的资本。
输入格式 第一行输入一个整数 n,w,k。
以下 n 行有 n 个项目,每一行有两个值 Ai的值是投资获取的利润,Bi的值是启动该项目的最小资本。
输出格式 输出一个整数,输出最大化后的资本。
#include<bits/stdc++.h>
using namespace std;
struct node {
int a;
int b;
};
struct cmp {
bool operator()(const node& p1, const node& p2) {
return p1.b < p2.b;
}
};
int solve(int w, int k, vector<node>& p) {
priority_queue<node, vector<node>, cmp> heap;
for (node& p : p) {
heap.push(p);
}
for (int i = 0; i < k; i++) {
vector<node> c;
while (!heap.empty() && heap.top().b <= w) {
c.push_back(heap.top());
heap.pop();
}
if (c.empty()) {
break;
}
node s = *max_element(c.begin(), c.end(), [](const node& p1, const node& p2) {
return p1.b < p2.b;
});
w += s.a;
}
return w;
}
int main() {
int n, w, k;
cin >> n >> w >> k;
vector<node> p(n);
for (int i = 0; i < n; i++) {
cin >> p[i].a >> p[i].b;
}
int maxb = solve(w, k, p);
cout << maxb << endl;
return 0;
}
WA 20