本题是一道贪心题目
首先计算出 没有JARVIS支持时，每种插槽（Ci个）应该安装哪些模块，可以使总威力最大。
显然每种插槽按威力从大到小选Ci个即可。（注意只从无需JARVIS支持的模块中选）
其次，考虑K个JARVIS支持"点数"，应该分配给哪些插槽。
这一步也是贪心，我们只要每次都分配给“收益最大”的插槽即可。
如果我们分配给第i种插槽，那么提升就是第i种插槽尚未安装的模块中威力最大的 减去 第i种插槽已经安装的模块中威力最小的。于是遍历所有插槽种类，从中选收益最大的即可。
以上是基本的贪心思路，不过实际要考虑很多边界情况。比如模块数量不足、有JARVIS的模块威力反而不如没有JARVIS的模块等等。
using namespace std;
int TT; int N,M,K;//N个武器 M个插槽 K个jarvis支持
int vectorSize(vector V,int n){ int sum = 0; for(int i = 0;i
bool cmp(int x1, int x2){ return x1>x2; }
struct Node{ vector T0;//储存 vector T1;//储存 }; vector P;
int C[maxn2]; int pre_cnt[maxn2];//第i个武器插槽不使用JARVIS支持的威力
int main (){ scanf("%d",&TT); while(TT--){
scanf("%d%d%d",&N,&M,&K);//N个武器 M个武器插槽 K个jarvis支持
P.resize(M+1);//
for(int i = 0;i<=M;i++) P.clear();
for(int i = 0;i<N;i++)
{
int temp_vv,temp_pp,temp_tt;
scanf("%d%d%d",&temp_vv,&temp_pp,&temp_tt);
if(temp_tt == 0) P[temp_pp].T0.push_back(temp_vv);//最好是把T0补0至Ci一样多 这样少了很多处理的判断
if(temp_tt == 1) P[temp_pp].T1.push_back(temp_vv);
}
for(int i = 1; i <= M; i++){
scanf("%d",&C[i]);
}
//若T0<Ci
//最好是把T0补0至Ci一样多 这样少了很多处理的判断
//判断有：直接加上T1的第一个字母或者是替换。
for(int i = 0;i <= M; i++){
int T0_size = P[i].T0.size();
for(int j = 0; j<C[i]-T0_size; j++) P[i].T0.push_back(0);
}
for(int i = 1; i<=M;i++){
sort(P[i].T0.begin(),P[i].T0.end(),cmp);
sort(P[i].T1.begin(),P[i].T1.end(),cmp);
// for(int j = 0;j
vector<int> Profit;
Profit.clear();
for(int i = 1; i<=M;i++){//第i个武器插槽
int size_0 = P[i].T0.size();//不需要JARVIS支持的武器个数
int size_1 = P[i].T1.size();//需要JARVIS支持支持的武器的个数
pre_cnt[i] = vectorSize(P[i].T0,C[i]);;//第i个武器插槽不使用JARVIS支持的总威力
//开始替换
for(int j = 0;j<size_1;j++){
if((C[i]-j-1 >= 0)&&P[i].T1[j] - P[i].T0[C[i]-j-1] > 0) Profit.push_back(P[i].T1[j] - P[i].T0[C[i]-j-1]);
}
}
int Profit_sum = 0;
//取前K个正的Profit作为利息的总值。
//for(int i = 0;i<Profit.size();i++) printf("%d \n",Profit[i]);
sort(Profit.begin(),Profit.end(),cmp);
K = min(Profit.size(),K);
for(int i = 0; i < K; i++) Profit_sum+=Profit[i];
for(int i = 1; i <= M; i++) Profit_sum+=pre_cnt[i];
printf("%d\n",Profit_sum);
}
}
