P1080国王游戏

待我称王封你为后i 2021-11-11 01:48 362阅读 0赞

[传送][Link 1]

![1605842-20190713132457405-949764933.png][]

![1605842-20190713132545267-142109246.png][]

![1605842-20190713132709417-1922662944.png][]

最大值最小什么的一看就是二分了qwq

然鹅并不知道怎么检查，所以我们换个思路

我们要求出最小的最大值，这肯定和大臣的排列有关，会不会有什么规律？

先看看只有两个大臣的情况

排列：1 2，ans1=max\{a0/b1,a0a1/b2\}

排列：2 1，ans2=max\{a0/b2,a0a2/b1\}

显然a0/b1<a0a2/b1,a0/b2<a0a1/b2,所以最大值取决于a0a1/b2和a0a2/b1

为了让最大值最小，当ans1>ans2的时候，我们就会调换1，2的顺序

所以就是a0a1/b2>a0a2/b1,也就是a1b1>a2b2的时候就会调换。

综上可得按照a\*b从小到大排序

其实这个题的难点不在排序思路，在于高精。

a,b<10000,n<1000,最坏情况ans=100001000,爽

建议结合代码食用

#include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    ll read()
    {
        char ch=getchar();
        ll x=0;bool f=0;
        while(ch<'0'||ch>'9')
        {
            if(ch=='-')f=1;
            ch=getchar();
        }
        while(ch>='0'&&ch<='9')
        {
            x=(x<<3)+(x<<1)+(ch^48);
            ch=getchar();
        }
        return f?-x:x;
    }
    struct rr
    {
        ll a,b;
    }ren[1009];
    ll n,aa,bb,sa[7009],now[7009],ma[7009],lenm=1,lens=1,lenn=1;//sa记录大臣们左手上的数的乘积，now记录当前大臣的金币，ma记录最大值
    bool cmp(rr t,rr w)
    {
        return t.a*t.b<w.a*w.b;
    }
    //以下是高精
    void cheng(ll k)//高精乘
    {
        sa[1]*=k;
        for(int i=2;i<=lens;i++)
        {
            sa[i]=sa[i-1]/10+sa[i]*k;
            sa[i-1]%=10;
        }
        while(sa[lens]>=10)
        {
            lens++;
            sa[lens]=sa[lens-1]/10;
            sa[lens-1]%=10;
        }
    }
    void chu(ll k)
    {
        int j=0,x=0;
        memset(now,0,sizeof(now));
        for(int i=lens;i>=1;i--)
        {
            j++;
            x=x*10+sa[i];
            now[j]=x/k;
            x=x-now[j]*k;
        }
        for(int i=1;i<=j/2;i++)//由于高精除单精是从第一位表示高位，所以要把now反过来，注意是i<=j/2,不是i<=j
          {
              int tmp=now[i];
              now[i]=now[j-i+1];
              now[j-i+1]=tmp;
          }
        while(now[j]==0&&j>1)
          j--;
        lenn=j;   
    }
    void max_()//进行比较
    {
        if(lenn>lenm)
        {
            for(int i=lenn;i>=1;i--)
             ma[i]=now[i];
             lenm=lenn;//别漏了
            return ; 
        }
        if(lenn<lenm) return ;
        for(int i=lenn;i>=1;i--)
        {
            if(now[i]<ma[i])
             break;
            if(now[i]>ma[i])//找到第一位比ma对应位小的
            {
                for(int j=i;j>=1;j--)
                {
                    ma[j]=now[j];
                }
                return ;
            } 
        }
        return ;
    }
    int main()
    {
        sa[1]=1;
        n=read();ren[0].a=read();ren[0].b=read();
        for(int i=1;i<=n;i++)
         ren[i].a=read(),ren[i].b=read();
        sort(ren+1,ren+1+n,cmp);    
        for(int i=1;i<=n;i++) 
        {   
           cheng(ren[i-1].a);
            chu(ren[i].b);
            max_();  
        }
        for(int i=lenm;i>=1;i--)
          printf("%lld",ma[i]);
    }

转载于:https://www.cnblogs.com/lcez56jsy/p/11180375.html

[Link 1]: https://www.luogu.org/problemnew/show/P1080
[1605842-20190713132457405-949764933.png]: /images/20211109/badacab633024f8b9dd28a43cfc8bda3.png
[1605842-20190713132545267-142109246.png]: /images/20211109/e561c39019bb4c1aba2d64a61384f106.png
[1605842-20190713132709417-1922662944.png]: /images/20211109/ffd987a8074e44fab92eb06af074aaca.png