求调
查看原帖
求调
1349478
tangyiqi楼主2024/7/9 09:35

哈喽,各位路过的老爷们,今天我来向你们寻求帮助了,不知道为什么,我认为时间复杂度挺高的,会出现TLE,但是,恰恰相反,#2已经AC了,但 #1 #3 #4 #5 怎么也AC不了,求调,谢谢大家的帮助。好了废话不多说,直接上代码。谢谢大家啦

#include <bits/stdc++.h>
using namespace std;
int n,v;
struct coin{
	int heavy;
}a[40];
bool cmp(coin a,coin b);
int main() {
	scanf("%d%d",&v,&n);
	for(int i = 0;i<n;i++)scanf("%d",&a[i].heavy);
	sort(a,a+n,cmp);
	int c;
	for(int i = 0;i<n;i++){
		if(v<=0)break;
		v-=a[i].heavy;
		c = i;
	}
	if(v<0){
		v+=a[c].heavy;
		for(int i = c;i<n;i++){
			if(v == a[i].heavy){
				v-=a[i].heavy;
			}
		}
		int max = a[c].heavy;
		for(int i = c+1;i<n;i++){
			if(a[i].heavy>max && a[i].heavy<=v){
				max = a[i].heavy;
				
			}
		}
		for(int i = c+1;i<n;i++){
			if(a[i].heavy == max)v-=a[i].heavy;
		}
		for(int i = 0;i<n;i++){
			if(v>0){
				max = a[c].heavy;
				for(int i = c+1;i<n;i++){
					if(a[i].heavy>max && a[i].heavy<=v){
						max = a[i].heavy;
					}
				}
				for(int i = c+1;i<n;i++){
					if(a[i].heavy == max)v-=a[i].heavy; 
				}
			}
		}
	}
	printf("%d",v);
	return 0;
}
bool cmp(coin a,coin b){
	return a.heavy>b.heavy;
}
2024/7/9 09:35
加载中...