最后一点WA了,求dalao
查看原帖
最后一点WA了,求dalao
358467
Hz_pro楼主2022/8/12 14:25

废话不多说,上代码

#include<bits/stdc++.h>
using namespace std;
int a[10005],b[10005],lena,lenb,c[20005],len;
string s1,s2;
bool pd()
{
	if(lena!=lenb)return lena>lenb;
	for(int i=lena;i>0;i--)
	if(a[i]!=b[i])return a[i]>b[i];
	return 1;
}
void print()
{
	for(int i=max(len,1);i>0;i--)
	printf("%d",c[i]);puts("");
}
int main()
{
	freopen("1.in","r",stdin);
	freopen("1.out","w",stdout);
	cin>>s1>>s2;
	for(int i=s1.size()-1;i>=0;i--)
	a[++lena]=s1[i]-48; 
	for(int i=s2.size()-1;i>=0;i--)
	b[++lenb]=s2[i]-48;
	len=max(lena,lenb);
	for(int i=1;i<=len;i++)
	c[i]+=a[i]+b[i],c[i+1]=c[i]/10,c[i]%=10;
	if(c[len+1])len++;
	print();
	bool f=pd();
	if(f)
	{
		for(int i=1;i<=len;i++)
		c[i]=a[i]-b[i];
	}
	else
	{
		putchar('-');
		for(int i=1;i<=len;i++)
		c[i]=b[i]-a[i];
	}
	for(int i=1;i<=len;i++)
	if(c[i]<0)c[i]+=10,c[i+1]--;
	while(!c[len])len--;
	print();
	len=lena+lenb;
	memset(c,0,sizeof(c));
	for(int i=1;i<=lena;i++)
	for(int j=1;j<=lenb;j++)
	c[i+j-1]+=a[i]*b[j];
	for(int i=1;i<=len;i++)
	c[i+1]+=c[i]/10,c[i]%=10;
	if(!c[len])len--;
	print();
	if(!f)
	{
		puts("0");
		for(int i=max(lena,1);i>0;i--)
		printf("%d",a[i]);return 0;
	}
	for(int i=lena-lenb+1;i>0;i--)
	if(i>lena)putchar('0');
	else
	{
		int l=0,r=9;
		while(l<r)
		{
			int mid=(l+r+1)/2;
			for(int j=1;j<=lenb;j++)
			c[j]=b[j]*mid;c[lenb+1]=0;
			for(int j=1;j<=lenb;j++)
			c[j+1]+=c[j]/10,c[j]%=10;
			if(c[lenb+1])
			{
				if(lena-i+1<=lenb)r=mid-1;
				else
				{
					bool f=0;int x=lenb+1;
					for(int j=lena;x;j--,x--)
					if(a[j]>c[x]){f=1;l=mid;break;}
					else if(a[j]<c[x]){f=1;r=mid-1;break;}
					if(!f)l=mid;
				}
			}
			else
			{
				if(lena-i+1>lenb)l=mid;
				else
				{
				bool f=0;int x=lenb;
				for(int j=lena;x;j--,x--)
				if(a[j]>c[x]){f=1;l=mid;break;}
				else if(a[j]<c[x]){f=1;r=mid-1;break;}
				if(!f)l=mid;
				}
			}
		}
		if(!(!l&&f))
		{
			f=0;
			printf("%d",l);int x=lenb;
			for(int j=i+lenb-1;x;j--,x--)
			a[j]-=b[x]*l;
			for(int j=i;j<=lena;j++)
			while(a[j]<0)a[j]+=10,a[j+1]--;
			while(!a[lena]&&lena>0)lena--;
		}
	}
	puts("");
	for(int i=max(lena,1);i>0;i--)printf("%d",a[i]);
	return 0;
}

2022/8/12 14:25
加载中...