只有三个TLE,怀疑是高精度的问题,求调
查看原帖
只有三个TLE,怀疑是高精度的问题,求调
95186
baen楼主2023/10/21 01:08
#include<bits/stdc++.h>
using namespace std;
int a[10000000],b[100],c[10000000],ans[10000000]={0};
int n,l1=0,l2,l3=0,l4=0;
int i,j,l;
struct lr
{
	int left,right;
}num[1005];
void max()
{
	if(l4>l3)
	return;
	else if(l4<l3)
	{
		l4=l3;
		A:for(j=0;j<=l3;j++)
		ans[j]=c[j];
		return;
	}
	else
	{
		for(j=l3;j>=0;j--)
		{
			if(c[j]>ans[j])
			goto A;
		}
		return;
	}
}
void mul()
{
	long long mull=num[i].left;
	l2=-1;
	while(mull!=0)
	{
		b[++l2]=mull%10;
		mull/=10;
	}
	if(l1<=l2||l1+l2<=17)
	{
		mull=0;
		for(j=0;j<=l1;j++)
		mull+=a[j]*pow(10,j);
		mull*=num[i].left;
		l1=-1;
		while(mull!=0)
	    {
			a[++l1]=mull%10;
			mull/=10;
	    }
	    return;
	}
	memset(c,0,sizeof(c));
	for(j=0;j<=l2;j++)
	{
		for(l=0;l<=l1;l++)
		{
			c[l+j]+=a[l]*b[j];
			if(c[l+j]>10)
			{
				c[l+j+1]+=c[l+j]/10;
				c[l+j]%=10;
			}
		}
	}
	if(c[l1+l2+1]>0)
	l1=l1+l2+1;
	else
	l1=l1+l2;
	for(j=0;j<=l1;j++)
	a[j]=c[j];
	return;
}
void div()
{
	long long divv=num[i].right;
	l2=-1;
	while(divv!=0)
	{
		b[++l2]=divv%10;
		divv/=10;
	}
	if(l1<=l2||l1<=18)
	{
		divv=0;
		for(j=0;j<=l1;j++)
		divv+=a[j]*pow(10,j);
		divv/=num[i].right;
		c[0]=divv;
		l3=0;
		return;
	}
	else
	{
		l3=-1;
		divv=0;
		for(l=0;l<=l2-1;l++)
		divv+=a[l1-l2+1+l]*pow(10,l);
		for(j=l1-l2;j>=0;j--)
		{
			divv=divv*10+a[j]; 
			if(divv/num[i].right>0||(divv/num[i].right>=0&&j<l1-l2))
			{
				c[++l3]=divv/num[i].right;
				divv%=num[i].right;
			}
		}
		return;
	}
}
inline bool cmp(lr x,lr y)
{
	return x.left*x.right<y.left*y.right;
}
int main()
{
	int k;
	memset(a,0,sizeof(a));
	cin>>n;
	cin>>num[0].left>>num[0].right;
	k=num[0].left;
	l1=-1;
	while(k!=0)
	{
		a[++l1]=k%10;
		k/=10;
	 } 
	for(i=1;i<=n;i++)
	cin>>num[i].left>>num[i].right;
	sort(num+1,num+n+1,cmp);
	for(i=1;i<=n;i++)
	{
		div();
		max();
		mul();
	}
	for(i=0;i<=l4;i++)
	cout<<ans[i];
	return 0;
}
2023/10/21 01:08
加载中...