求助,贪心思路应该是对的,但是加了高精度之后就全WA了,还有4个MLE,怎么办?
查看原帖
求助,贪心思路应该是对的,但是加了高精度之后就全WA了,还有4个MLE,怎么办?
275373
Mayoker楼主2022/7/18 15:16
#include<bits/stdc++.h>
using namespace std;
const int N=4e4+10;
int n,ans[N],sum=1;
int a[N],c[N]; 

void mul1(int a[],int b,int c[]){
	for(int i=1;i<=a[0];i++) c[i]=a[i]*b;
	for(int i=1;i<=c[0];i++)
		c[i+1]+=c[i]/10,c[i]%=10;
	
	if(c[c[0]+1]) c[0]++;
	
	while(c[c[0]]>=10){
		c[c[0]+1]=c[c[0]]/10;
		c[c[0]]%=10;
		c[0]++;
	}
	
	while(c[c[0]]==0&&c[0]>1) c[0]--; 
	for(int i=c[0];i>=1;i--) a[i]=c[i];
	a[0]=c[0];
} 

int div(int a[],int b,int c[]){
	int t=0;
	c[0]=a[0]; 
	//t为余数 
	for(int i=a[0];i>=1;i--){
		t=t*10+a[i];
		c[i]=t/b;
		t%=b;
	}
	
	while(c[c[0]]==0&&c[0]>1) c[0]--; 
	return t;
}

struct player{
	int left;
	int right;
};
player a1[N];

int cmp1(int c[],int ans[]){
	if(c[0]<ans[0]) return -1;
	if(c[0]>ans[0]) return 1;
	for(int i=c[0];i>=1;i--){
		if(c[i]<ans[i]) return -1;
		if(c[i]>ans[i]) return 1;
	}
	return 0;
}

bool cmp(const player &a,const player &b){
	return a.left*a.right<b.left*b.right;
}

void give1(int c[],int ans[]){
	for(int i=0;i<=a[0];i++) ans[i]=c[i];
}

int main(){
	cin>>n;
	a[0]=a[1]=1;
	for(int i=1;i<=n+1;i++){
		cin>>a1[i].left>>a1[i].right;
	}
	sort(a1+2,a1+2+n,cmp);
	for(int i=2;i<=n+1;i++){
		for(int j=i-1;j>=1;j--){
			memset(c,0,sizeof(c));
			mul1(a,a1[j].left,c);
		}
		memset(c,0,sizeof(c));
		div(a,a1[i].right,c);
		if(cmp1(c,ans)) give1(c,ans);
	}
	for(int i=ans[0];i>=1;i--) cout<<ans[i];
	return 0;
}
2022/7/18 15:16
加载中...