#21,#26WA,求调
查看原帖
#21,#26WA,求调
1371831
lijunxiang2956楼主2025/7/23 20:59

不知道咋回事,就是过不了,改了好久,写了注释帮助理解代码,求调

#include<iostream>
#include<algorithm>
using namespace std;
long long n,m,num1_times=0,nums=1,ans=0;  //num1_times是武器1的适配材料个数,ans是最少钱数
struct material{
	long long weapons,coin,time;     //分别对应适配武器个数,更改适配武器所需金币,出现次数
}a[10001]={0};
struct c{
	long long num,times;        //分别对应武器标号,适配武器材料所出现的次数
}b[10001]={0};
bool cmp(c x,c y){
	return x.times>y.times;     //将b数组依照适配武器材料所出现的次数降序排序
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) b[i].num=i;  //将b数组的武器进行标号
	for(int i=1;i<=m;i++){
		cin>>a[i].weapons>>a[i].coin;
		if(a[i].weapons==1){
			num1_times++; 
			continue;  //记录适配武器1的材料个数,continue是为了不重复记录,影响后面求答案的时候将第1种武器的次数参与判断
		}
		b[a[i].weapons].times++;     //表示适配武器材料出现次数加1
	}
	sort(b+1,b+1+n,cmp); 
	for(int i=1;i<=m;i++){                //统计出现次数,方便下面排序
		for(int j=1;j<=n;j++){
			if(b[j].num==a[i].weapons){
				a[i].time=b[j].times;
				break;
			}
		}
	}
	for(int i=1;i<m;i++){      //排序,优先按花费金币数量从小到大排序,如果相等就按出现次数大小从大到小排序,优先出现次数多的
		for(int j=i+1;j<=m;j++){
			if(a[i].coin>a[j].coin) swap(a[i],a[j]);
			else if(a[i].coin==a[j].coin && a[i].time<a[j].time) swap(a[i],a[j]);
		}
	}
	while(num1_times<=b[1].times){//因为b[1].times一定最大,所以直接比较,如果大于了,就说明武器1的适配材料为当前最多
		for(int j=1;num1_times<=b[1].times;j++){
			if(a[j].weapons==1) continue;    //如果适配武器为1,直接忽略
			num1_times++;
			ans+=a[j].coin;            //将材料适配武器变为1,加上所花金币,适配武器1的材料数+1
			for(int k=1;k<=n;k++){     //将对应材料的出现次数-1
				if(b[k].num==a[j].weapons){
					b[k].times--;
					break;
				}
			}
			sort(b+1,b+1+n,cmp);  //每一次都将出现次数降序排序,保证b[1].times最大
		}
	}
	cout<<ans;    //输出
	return 0;
}
2025/7/23 20:59
加载中...