萌新求助!! 只有80分 调了一下午也调不对
查看原帖
萌新求助!! 只有80分 调了一下午也调不对
383601
shijihong楼主2021/12/14 17:44
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
struct node{int x,y;};
node a[1005],b[1005];
void msort(int l,int r){
	if(l==r) return;
	int mid=(l+r)/2,i=l,j=mid+1,k=l;
	msort(l,mid),msort(mid+1,r);
	while(i<=mid and j<=r){
		if(ll(a[i].x*a[i].y)>=ll(a[j].x*a[j].y)) b[k++]=a[j++];
		else b[k++]=a[i++];
	}
	while(i<=mid) b[k++]=a[i++];
	while(j<=r) b[k++]=a[j++];
	for(int p=l;p<=r;p++) a[p]=b[p];
}
int num[2005],res[2005],ans[2005];
void mul(int x){
	for(int i=1;i<=2000;i++) num[i]*=x;
	for(int i=2000;i>=1;i--){
		num[i-1]+=num[i]/10;
		num[i]%=10;
	}
}
void div(int x){
	memset(res,0,sizeof(res));
	int i=1,left=0;
	while(!num[i])i++;
	while(i<=2000){
		int temp=left;
		while(temp<x) temp=temp*10+num[i++];
		res[i-1]=temp/x;
		left=temp%x;
	}
}
bool great(){
	for(int i=1;i<=2000;i++) 
		if(res[i]>ans[i]) return true;
		else if(res[i]<ans[i]) return false;
	return true;
}
void print(){
	int z=1;
	while(!ans[z] and z<=2000) z++;
    if(z>2000) cout<<0;
	else for(int i=z;i<=2000;i++) cout<<ans[i];
	cout<<endl;
}
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n+1;i++) cin>>a[i].x>>a[i].y;
	msort(2,n+1);
	num[2000]=1;
	for(int i=2;i<=n+1;i++){
		mul(a[i-1].x);
		div(a[i].y);
		if(great()) for(int i=1;i<=2000;i++) ans[i]=res[i];
	}
	print();
}
2021/12/14 17:44
加载中...