贪心，将价值减去价格，每次挑选最大的即可（注意！不需要拿满 kkk 件！如果处理这个废品后的收益小于等于 000 就不要再拿了） 时间复杂度：O(Nlog⁡N)O(N\log N)O(NlogN). 当然，你也可以使用堆来实现在线得出最优解（O(Nlog⁡N)O(N\log N)O(NlogN)），或者用背包DP（O(N×Vi)O(N\times V_i)O(N×Vi )），以下给出背包DP的代码：

#include<bits/stdc++.h> using namespace std; int main(){ int n,k,q,w; cin>>n>>k; char c; vector <int> a,b; while(n--){ cin>>c>>q>>w; if(c=='A') a.push_back(q-w); else b.push_back(q-w); }

#include<bits/stdc++.h> using namespace std; struct f { int y=0; int m=0; int c=0; }; struct x { int y=0; int m=0; int c=0; }; bool cmp(f a,f b) { return a.c>b.c; } bool cpp(x a,x b) { return a.c>b.c; } int main() { int a,b; cin>>a>>b; f f[a]; x x[a]; for(int i=0;i<a;i++) { char c; cin>>c; if(c=='A') { cin>>f[i].y>>f[i].m; f[i].c=f[i].y-f[i].m; } else if(c=='B') { cin>>x[i].y>>x[i].m; x[i].c=x[i].y-x[i].m; } } sort(f,f+a,cmp); sort(x,x+a,cpp); int e=0; for(int i=0;i<b;i++) { e+=x[i].c; e+=f[i].c; } cout<<e; return 0; }

#include<bits/stdc++.h> using namespace std; #define int long long signed main() { int n,k,v,p; cin>>n>>k; vector <int> a,b; while(n--){ char c; cin>>c>>v>>p; if(c=='A') a.push_back(v-p); else b.push_back(v-p); } sort(a.begin(),a.end(),greater <int> ()); sort(b.begin(),b.end(),greater <int> ()); int cnt=0; for(int i=0;i<k;i++){ if(a[i]>0)cnt+=a[i]; if(b[i]>0)cnt+=b[i]; } cout<<cnt; return 0; }