官方题解 | 废品回收

贪心，将价值减去价格，每次挑选最大的即可（注意！不需要拿满 $k$ 件！如果处理这个废品后的收益小于等于 $0$ 就不要再拿了）

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm> 
using namespace std;
vector <int> a, b;
int main(){
	cin.tie(nullptr) -> sync_with_stdio(0);
	cout.tie(nullptr) -> sync_with_stdio(0);
	int n, m;
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		char c;
		int x, y;
		cin >> c >> x >> y;
		if(c == 'A') a.push_back(x - y);
		else b.push_back(x - y);
	}
	sort(a.begin(), a.end(), greater <int>());//排序，这样就能挑最大的
	sort(b.begin(), b.end(), greater <int>());
	int ct = 0;
	for(int i = 0; i < m && i < a.size() && a[i] > 0; i++) ct += a[i];//拿取
	for(int i = 0; i < m && i < b.size() && b[i] > 0; i++) ct += b[i];
	cout << ct;

	return 0;
}

时间复杂度：$O(N\log N)$.

当然，你也可以使用堆来实现在线得出最优解（$O(N\log N)$），或者用背包DP（$O(N\times V_i)$），以下给出背包DP的代码：

#include<bits/stdc++.h>
using namespace std;
int A_v[1005],B_v[1005];
bool cmp(int a,int b){return a > b;}
int main(){
    int n,k; cin >> n >> k;
    int A_idx = 1,B_idx = 1;
    while(n--){
        char op; cin >> op;
        int v,p; cin >> v >> p;
        if(op == 'A') A_v[A_idx++] = v - p;
        else B_v[B_idx++] = v - p;
    }
    sort(A_v + 1,A_v + A_idx + 1,cmp);
    sort(B_v + 1,B_v + B_idx + 1,cmp);
    long long ans = 0;
    for(int i = 1;i <= k;i++){
        if(A_v[i] > 0) ans += A_v[i];
        else break;
    }
    for(int i = 1;i <= k;i++){
        if(B_v[i] > 0) ans += B_v[i];
        else break;
    }
    cout << ans;
    return 0;
}