数据2 wa 7RE 还有3个TLE,高精度除以高精度会超时吗
查看原帖
数据2 wa 7RE 还有3个TLE,高精度除以高精度会超时吗
241782
Echo_j楼主2020/7/1 15:04
#include <bits/stdc++.h>

using namespace std;
const int maxn = 2e4+10;
int A[maxn];
int ej = 1;
int ans[maxn] = {0};
struct P
{
    int a;
    int b;
}p[maxn];
struct Rule
{
    bool operator()(const P &p1,const P &p2)
    {
        return p1.a*p1.b <= p2.a*p2.b;
    }
};
void chengfa(int x)
{
	int B[maxn];
	int C[maxn];
	memset(B,0,sizeof(B));
	memset(C,0,sizeof(C));
	while(x)
	{
		B[++B[0]] = (x%10);
		x/=10;
	}
	for(int i=1;i<=B[0];i++)
	{
		int tmp = 0;
		for(int j=1;j<=ej;j++)
		{
			int t = i+j-1;
			C[t]  +=  A[j]*B[i] + tmp;//这次乘积 + 上次乘积 + 进位
		    tmp =  C[t]/10;//取进位
			C[t]%=10;
		}
		C[i+ej] = tmp;
	}
	ej = B[0]+ej+1;
	while(C[ej]==0) ej--;
	/*for(int i=ej;i>0;i--)
    {
        cout<<C[i];
    }
    cout<<endl;*/
	for(int i=ej;i>0;i--)
	{
		A[i] = C[i];
		//cout<<A[i];
	}
	//cout<<endl;
	A[0] = ej;
}
int cmp(int A2[maxn],int B[maxn])
{
    if(A2[0]>B[0]) return 1;
    else if(A2[0]<B[0]) return -1;
    else
    {
        for(int i=A2[0];i>=1;i--)
        {
            if(A2[i]>B[i]) return 1;
            else if(A2[i]<B[i]) return -1;
        }
        return 0;
    }
}
void duiqi(int B[maxn],int tmp[maxn],int d)//把数组B向右移动d-1位并且存入数组tmp里面
{
    for(int i=d;i<=B[0]+d-1;i++)
    {
        tmp[i] = B[i-d+1];
    }
    tmp[0] = B[0] + d - 1;//注意
}
void chufa(int x)
{
   /* printf("A: ");
    for(int i=A[0];i>0;i--)
    {
        cout<<A[i];
    }
        cout<<endl;*/
   int A2[maxn];
   int B[maxn];
   for(int i=A[0];i>0;i--)
   {
       A2[i] = A[i];
   }
   A2[0] = A[0];
   memset(B,0,sizeof(B));
   while(x)
   {
       B[++B[0]] = x%10;
       x/=10;
   }
   int C[maxn];//存商
    memset(C,0,sizeof(C));
    if(cmp(A2,B)<0)
    {

     C[0] = 1;
     C[1] = 0;
    }
    else if((A2,B)==0)
    {
       C[0] = 1;
       C[1]  = 1;
    }
    else if((A2,B)>0)
    {

        C[0] = A2[0] - B[0] +1;
     for(int i=C[0];i>0;i--)
    {
        int tmp[maxn];
        memset(tmp,0,sizeof(tmp));
        duiqi(B,tmp,i);//注意
         while(cmp(A2,tmp)>=0)
           {
               C[i]++;
               //从个位开始减
               for(int j=1;j<=A2[0];j++)
               {
                   if(A2[j]<tmp[j])
                   {
                       A2[j+1]--;
                       A2[j]+=10;
                   }
                   A2[j]-=tmp[j];
               }
               while(A2[A2[0]]==0&&A[0]>0)
               {
                   A2[0]--;
                // k--;
               }
           }
    }
       while(C[C[0]]==0&&C[0]>0)
        {
            C[0]--;
        }
    }
    if(cmp(ans,C)<0)
    {
         for(int i=C[0];i>0;i--)
    {
       ans[i] = C[i];
    }
    ans[0] =C[0];
    }

}
int main()
{
    std::ios::sync_with_stdio(false);
    int n;
    int ka;
    int kb;
    cin>>n;
    cin>>ka>>kb;
    for(int i=0;i<n;i++)
    {
      cin>>p[i].a>>p[i].b;
    }
    sort(p,p+n,Rule());
   /* for(int i=0;i<n;i++)
    {
      cout<<p[i].a<<" "<<p[i].b<<endl;;
    }*/
    while(ka)
    {
       A[ej++]=(ka%10);
       ka/=10;
    }
    ej--;
    A[0] = ej;
    for(int i=0;i<n;i++)
    {
       chufa(p[n-1].b);
       chengfa(p[i].a);
    }
    for(int i=ans[0];i>0;i--)
    {
        cout<<ans[i];
    }
    return 0;
}

2020/7/1 15:04
加载中...