题意:有一个国王和n个大臣,排成一列玩一个,每个人左右手分别有一个数值,每个人的分值定义为之前所有人左手的分值和除以自己右手的分值(下取整),国王始终站在最前面,现要你安排大臣的顺序,使得分值最大的大臣的分值尽量小

题解:

贪心+高精

按左右手乘积从小到大排序

所有数的乘积最大不超过\(10^{4000}\),码一发高精乘低精和高精除低精即可

注意:比较s和g时写成函数会wa,可能传指针的时候会有鬼畜的事情发生= =、

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define N 5000using namespace std;int g[N],f[N],s[N];struct Node { int a,b; bool operator < (const Node &x) const { return a*b
          
           '9')) ch=getchar(); if(ch=='-') o=-1; while(ch>='0' && ch<='9') x=10*x+ch-'0',ch=getchar(); return x*o;}void work(int u) { int a=p[u].a,b=p[u].b,x=0,flg=0; memset(s,0,sizeof(s)); for(int i=f[0]; i>=1; i--) { x=10*x+f[i]; if(x/b) { s[i]=x/b,x-=b*(x/b); if(!flg) flg=1,s[0]=i; } } if(g[0]
           
            =1; i--) { if(g[i]
            
             s[i]) break; } } x=0; for(int i=1; i<=f[0]; i++) { f[i]=f[i]*a+x; x=f[i]/10,f[i]%=10; } while(x) f[++f[0]]=x%10,x/=10;}int main() { int n=gi(),x=gi(),y=gi(); for(int i=1; i<=n; i++) { p[i].a=gi(),p[i].b=gi(); } sort(p+1,p+n+1); while(x) f[++f[0]]=x%10,x/=10; for(int i=1; i<=n; i++) work(i); if(!g[0]) printf("0"); else for(int i=g[0]; i>=1; i--) { printf("%d", g[i]); } return 0;}