问一道站外题目
  • 板块学术版
  • 楼主Hathtizzz
  • 当前回复5
  • 已保存回复5
  • 发布时间2024/1/13 11:46
  • 上次更新2024/1/13 14:45:10
查看原帖
问一道站外题目
1054564
Hathtizzz楼主2024/1/13 11:46

题目描述 小埋创建的公司即将开始IPO。为了更高的将价格将股票卖给风险投资公司,小埋希望在 IPO 之前公司开展一些项目增加自己的公司资本。由于资源有限,它只能在 IPO 之前完成最多 KK 个不同的项目。请帮助小埋设计完成最多 KK个不同的项目后得到的最大总资本的方式。

小埋有这样 nn 个项目。对于每个项目 i ,它都有一个纯利润 AiA_i ,和启动该项目需要的最小资本 BiB_i .

最初,小埋的资本为 ww。当你完成一个项目时,你将获得纯利润,且利润将被添加到你的总资本当中。

总而言之,从这 nn 个项目当中选择最多 KK 个不同的项目列表,以最大化最终的资本,并输出最终可获得的最多的资本。

输入格式 第一行输入一个整数 n,w,k。n,w,k。

以下 nn 行有 nn 个项目,每一行有两个值 AiA_i的值是投资获取的利润,BiB_i的值是启动该项目的最小资本。

输出格式 输出一个整数,输出最大化后的资本。

#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

2024/1/13 11:46
加载中...