做项目的最大收益问题

#include <bits/stdc++.h>
using namespace std;

struct P{
    int cost, w;
};

bool cmp(P a, P b){
    return a.cost < b.cost;
}

int main(){
    long n,w,k;
    cin>>n>>w>>k;
    P v[n];
    for(int i=0;i<n;i++)
        cin>>v[i].cost;
    for(int i=0;i<n;i++)
        cin>>v[i].w;
    sort(v, v+n, cmp);
    priority_queue<int> q;
    for(int i=0;i<n && k;i++){
        for(;k && v[i].cost>w;k--){
            if(q.empty()){
                cout<<w<<endl;
                return 0;
            }
            w += q.top();
            q.pop();
        }
        q.push(v[i].w);
    }
    for(;k && !q.empty();k--){
        w += q.top();
        q.pop();
    }
    cout<<w<<endl;
    return 0;
}

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

class Project{
public:
    Project(long x, long y)
    {
        cost = x;
        profit = y;
    }
    long cost;
    long profit;
};

struct minCostCmp{
    bool operator()(Project* p1, Project* p2)
    {
        return p1->cost > p2->cost; // 小根堆
    }
};
struct maxProfitCmp{
    bool operator()(Project* p1, Project* p2)
    {
        return p1->profit < p2->profit; // 大根堆
    }
};

int main()
{
    int n, k;
    long w;
    cin >> n >> w >> k;
    vector<long> costs(n, 0);
    for (int i=0; i<n; i++) cin >> costs[i];
    vector<long> profits(n, 0);
    for (int i=0; i<n; i++) cin >> profits[i];
    vector<Project*> projects(n, NULL);
    for (int i=0; i<n; i++)
    {
        projects[i] = new Project(costs[i], profits[i]);
    }
    priority_queue<Project*, vector<Project*>, minCostCmp> minCostHeap;
    priority_queue<Project*, vector<Project*>, maxProfitCmp> maxProfitHeap;
    for (int i=0; i<n; i++) minCostHeap.push(projects[i]);
    for (int i=0; i<k; i++)
    {
        while (!minCostHeap.empty() && minCostHeap.top()->cost <= w)
        {
            maxProfitHeap.push(minCostHeap.top());
            minCostHeap.pop();
        }
        if (maxProfitHeap.empty()) cout << w << endl;
        w += maxProfitHeap.top()->profit;
        maxProfitHeap.pop();
    }
    cout << w << endl;
    return 0;
}

来个Python3版本的

N, W, K = (int(_) for _ in input().strip().split())
if N <=0:
    print(W)
costs = [int(_) for _ in input().strip().split()]
profits = [int(_) for _ in input().strip().split()]
items = [(a, b) for a, b in zip(costs, profits)]
import heapq
heapq.heapify(items)  # 先把所有项目按照花费的小根堆组织起来
more_q = []  # 大根堆按照profits组织
# 循环 K 次选择 K 个项目
for i in range(K):
    # 把当前资金能做的项目从小根堆中弹出，并进入大根堆
    while len(items)>0 and items[0][0] <= W:
        one_item = heapq.heappop(items)
        heapq.heappush(
            more_q, (-one_item[1],) + one_item
        )  # 由于默认小根堆，所以把利润取反后push进小根堆，就是大根堆了
    # 循环结束时， one_item 是当前轮初始资金不能做的
    if len(more_q) == 0: # 如果大根堆没有元素了，代表当前的资金无法做任何项目了，可以提前停止了
        break

    # 从大根堆中取出一个项目做，并把收益加到资金中
    do_item = heapq.heappop(more_q)[1:]
    W +=  do_item[1]
print(W)

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int w = scanner.nextInt();
        int k = scanner.nextInt();
        scanner.nextLine();
        int[] casts = new int[n];
        int[] profits = new int[n];
        for (int i = 0; i < n; i++) {
            casts[i] = scanner.nextInt();
        }
        scanner.nextLine();
        for (int i = 0; i < n; i++) {
            profits[i] = scanner.nextInt();
        }
        long maxGains = getMaxGains(casts, profits, k, w);
        System.out.println(maxGains);
    }

    /**
     * @param casts   项目所需花费
     * @param profits 项目利润
     * @param k       可做项目个数
     * @param w       初始资金
     * @return
     */
    public static long getMaxGains(int[] casts, int[] profits, int k, int w) {
        long maxResult = w;
        //堆中存放索引，在数组中查找对应的利润和成本，可以把两个数组串联起来省去创建对象，优雅！
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                //小根堆，根据casts数组
                return casts[o1] - casts[o2];
            }
        });
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                //大根堆，根据profits数组
                return profits[o2] - profits[o1];
            }
        });
        for (int i = 0; i < casts.length; i++) {
            minHeap.offer(i);
        }
        //当堆不为空且堆顶元素花费小于等于成本时,把他转到利润堆中
        while (!minHeap.isEmpty() && casts[minHeap.peek()] <= w) {
            maxHeap.offer(minHeap.poll());
        }
        for (int i = 0; i < k; i++) {
            int profit = profits[maxHeap.poll()];
            maxResult += profit;
            w += profit;
            //更新堆
            while (!minHeap.isEmpty() && casts[minHeap.peek()] <= w) {
                maxHeap.offer(minHeap.poll());
            }
        }
        return maxResult;
    }
}

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
using Node = pair<long, long>;

int main(void) 
{
    long N, W, K;
    cin >> N >> W >> K;
    long *costs = new long[N];
    long *profits = new long[N];
    for (int i = 0; i < N; i++)
        cin >> costs[i];
    for (int i = 0; i < N; i++)
        cin >> profits[i];
    
    auto cmp1 = [](Node &a, Node &b){return a.first > b.first;};
    auto cmp2 = [](Node &a, Node &b){return a.second < b.second;};
    priority_queue<Node, vector<Node>, decltype(cmp1)> min_heap(cmp1);
    priority_queue<Node, vector<Node>, decltype(cmp2)> max_heap(cmp2);
    for (int i = 0; i < N; i++)
        min_heap.push({costs[i], profits[i]});
    
    while (K--) {
        while (!min_heap.empty() && min_heap.top().first <= W) {
            max_heap.push(min_heap.top());
            min_heap.pop();
        }
        if (max_heap.empty()) break;
        W += max_heap.top().second;
        max_heap.pop();
    }
    cout << W << endl;
}

#include<bits/stdc++.h>
using namespace std;
struct Project{
    int cost;
    int profit;
    Project(int a,int b):cost(a),profit(b){}
};
struct cmp1{
    bool operator()(Project p,Project q)
    {
        return p.cost>q.cost;
    }
};
struct cmp2{
    bool operator()(Project p,Project q)
    {
        return p.profit<q.profit;
    }
};
int main()
{
    int N,K;
    long W;
    cin>>N>>W>>K;
    // 最小花费 小顶堆
    priority_queue<Project,vector<Project>,cmp1>pq_costMin;
    // 最大利润 大顶堆
    priority_queue<Project,vector<Project>,cmp2>pq_ProfitMax;
    vector<int>cost(N,0);
    vector<int>profit(N,0);
    for(int i=0;i<N;++i)
        cin>>cost[i];
    for(int i=0;i<N;++i)
        cin>>profit[i];
    for(int i=0;i<N;++i)
         pq_costMin.push(Project(cost[i],profit[i]));
    while(!pq_costMin.empty() && pq_costMin.top().cost<=W)
    {
        pq_ProfitMax.push(pq_costMin.top());
        pq_costMin.pop();
    }
    while(K>0 && !pq_ProfitMax.empty())
    {
        Project cur = pq_ProfitMax.top();
        pq_ProfitMax.pop();
        W += cur.profit;
        --K;
        while(!pq_costMin.empty() && pq_costMin.top().cost<=W)
        {
            pq_ProfitMax.push(pq_costMin.top());
            pq_costMin.pop();
        }

    }
    cout<<W;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

struct Node{
    int profit;
    int cost;
};
struct tmp1{
    bool operator() (Node a, Node b){
        return a.profit < b.profit; //大顶堆
    }
};
struct tmp2{
    bool operator() (Node a, Node b){
        return a.cost > b.cost; //小顶堆
    }
};

int main(){
    long n, money, k;
    cin >> n >> money >> k;
    vector<Node> pj(n);
    for(int i = 0;i<n;i++) cin >> pj[i].cost;
    for(int i = 0;i<n;i++) cin >> pj[i].profit;

    priority_queue<Node, vector<Node>, tmp1> maxPHeap;
    priority_queue<Node, vector<Node>, tmp2> minCHeap;
    for(int i=0; i<n; i++){
        minCHeap.push(pj[i]);
    }
    for(int i=0; i<k; i++){
        while(minCHeap.top().cost <= money && !minCHeap.empty()){
            maxPHeap.push(minCHeap.top()); minCHeap.pop();
        }
        if(!maxPHeap.empty()){
            int get = maxPHeap.top().profit; maxPHeap.pop();
            money += get;
        } else break;
    }
    cout << money;
    return 0;
}