贪心RE,求调
查看原帖
贪心RE,求调
189610
APolaris楼主2024/12/2 15:53
#include<iostream>
#include<cstdio>
#include<cmath>

using namespace std;

int s[9],ans,sum;
int S[6][25];

void swap(int *a,int *b){
	int temp=*a;
	*a=*b;
	*b=temp;
}

void Sort(int a[],int n){
	for(int i=1;i<=n-1;i++){
		for(int j=1;j<=n-i;j++){
			if(a[j]>a[j+1])
				swap(&a[j],&a[j+1]);
		}
	}
}

int review(int a[],int L,int R){
	int i=L,j=R;
	if(i==j){
		ans+=a[i];
		return ans;
	}
	if(a[j]>a[i]){
		a[j]-=a[i];
		ans+=a[i];
		review(a,i+1,j);
	}
	else if(a[j]==a[i]){
		ans+=a[i];
		if(j==i+1) return ans;
		review(a,i+1,j-1);
	}
	else{
		a[i]-=a[j];
		ans+=a[j];
		review(a,i,j-1);
	}
}

int main(){
	for(int i=1;i<=4;i++)
		scanf("%d",&s[i]);
	for(int i=1;i<=4;i++){
		ans=0;
		for(int j=1;j<=s[i];j++)
			scanf("%d",&S[i][j]);
		if(s[i]==1) sum+=S[i][1];
		else{
			Sort(S[i],s[i]);
			int x=review(S[i],1,s[i]);
			sum+=x;
		}
			
	}
	printf("%d",sum);
	
	return 0;
	
}

ps:为什么贪心不是正解???

2024/12/2 15:53
加载中...