推那个贪心直接自己推就好了，最后推出来最优解在a*b按从小到大排序中
就在读入完后排序 再按排好的顺序一个一个比较出这个方案中得到最多钱的值 这个值就是答案
推导：略 （真的不是我想咕咕咕） 
最最最最最最最重要的是我打这题时的艰难改的过程
因为对模版理解不彻底 导致自己背着打的时候全都是错误！！！！！
我的一些错误或者是需要注意的地方
- 压位之后的数组从左往右是从低位到高位排序的 eg：123456存进去是这样 [1234] [56] 所以比较是要从高位到低位逐一比较(理解了的应该都晓得QAQ)
- 然后要用高精/低精 我开始懒得写高精/低精 然后就想的把那个低精转为高精去按高精/高精来搞，结果emmmmmmm过于慢了 因为高精/高精是挨个挨个减，然后那个除数太小了......
- 然后是一些低级错误QAQ j 打成 i 什么的
代码里的加还有减都用不到 主要是我想背一下，然后写题解的时候懒得删了
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define rg register 4 const int base=10000,power=4; 5 const int N=10000+5; 6 int n; 7 template<class t>void rd(t &x) 8 { 9 x=0;int w=0;char ch=0; 10 while(!isdigit(ch)) w|=ch=='-',ch=getchar(); 11 while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); 12 x=w?-x:x; 13 } 14 15 struct node{ 16 int a,b,c; 17 bool operator <(const node x) const{return c<x.c;} 18 }e[N]; 19 20 struct num{ 21 int a[N]; 22 num(){memset(a,0,sizeof(a));} 23 num(int x) 24 {//低精度转高精度 25 memset(a,0,sizeof(a)); 26 int t=0; 27 while(x) 28 { 29 a[++t]=x%base; 30 x/=base; 31 } 32 a[0]=t; 33 } 34 void print() 35 { 36 printf("%d",a[a[0]]); 37 for(rg int i=a[0]-1;i>0;--i) 38 printf("%0*d",power,a[i]);//这句的意思就是 如果输出的长度不足power的话就用0来补位 39 //例子:如果a[i]=12的话 而power=4 所以输出的是0012 40 printf(" "); 41 } 42 }p,pai,nw,ans; 43 //p是当前大臣左手的数 nw是当前大臣所得的钱 pai是累乘的积 44 bool operator <(const num &p,const num &q) 45 { 46 if(p.a[0]<q.a[0]) return 1; 47 if(p.a[0]>q.a[0]) return 0; 48 for(rg int i=p.a[0];i>0;--i)//从高位到低位逐一比较 49 if(p.a[i]!=q.a[i]) return p.a[i]<q.a[i]; 50 return 0; 51 } 52 53 num operator +(const num &p,const num &q)//高精+ 54 { 55 num c; 56 c.a[0]=max(p.a[0],q.a[0]); 57 for(rg int i=1;i<=c.a[0];++i) 58 { 59 c.a[i]+=p.a[i]+q.a[i]; 60 c.a[i+1]+=c.a[i]/base,c.a[i]%=base; 61 } 62 if(c.a[c.a[0]+1]) ++c.a[0]; 63 return c; 64 } 65 66 num operator -(const num &p,const num &q)//高精- 67 { 68 num c=p; 69 for(rg int i=1;i<=q.a[0];++i) 70 { 71 c.a[i]-=q.a[i]; 72 if(c.a[i]<0) --c.a[i+1],c.a[i]+=base; 73 } 74 while(c.a[0]>0&&!c.a[c.a[0]]) --c.a[0]; 75 return c; 76 } 77 78 num operator *(const num &p,const num &q)//高精* 79 { 80 num c; 81 c.a[0]=p.a[0]+q.a[0]-1; 82 for(rg int i=1;i<=p.a[0];++i) 83 for(rg int j=1;j<=q.a[0];++j) 84 { 85 c.a[i+j-1]+=p.a[i]*q.a[j]; 86 c.a[i+j]+=c.a[i+j-1]/base,c.a[i+j-1]%=base; 87 } 88 //while(c.a[0]>1&&!c.a[c.a[0]]) --c.a[0]; 89 while(c.a[c.a[0]+1]) ++c.a[0]; 90 return c; 91 } 92 93 num operator /(const num &p,const int &q)//高精/低精 94 { 95 num x; 96 int y=0; 97 for(rg int i=p.a[0];i>=1;--i) 98 { 99 y=y*base+p.a[i]; 100 if(y>=q) x.a[i]=y/q,y%=q; 101 } 102 x.a[0]=p.a[0]; 103 while(x.a[0]>=1&&!x.a[x.a[0]]) --x.a[0];//去前导0 104 return x; 105 } 106 107 int main() 108 { 109 //freopen("testdata.in-3.txt","r",stdin); 110 rd(n);int q; 111 for(rg int i=0;i<=n;++i) rd(e[i].a),rd(e[i].b),e[i].c=e[i].a*e[i].b; 112 sort(e+1,e+1+n); 113 pai=num(e[0].a); 114 for(rg int i=1;i<=n;++i) 115 { 116 p=num(e[i].a),q=e[i].b; 117 nw=pai/q,pai=pai*p; 118 if(ans<nw) ans=nw; 119 } 120 //pai.print(); 121 ans.print(); 122 return 0; 123 }
放一个高精/高精 （我开始打的时候把y.re()放进while里了QAQ）
1 num operator / (const num &p, const num &q) 2 { 3 num x, y; 4 for (int i = p.a[0];i >= 1;--i) //从最高位开始取数 5 { 6 y.add(p.a[i]); //把数添到末尾（最低位），这时候是高位在前，低位在后 7 y.re(); //把数反过来，变为统一的存储方式：低位在前，高位在后 8 while ( !(y < q) ) //大于等于除数的时候，如果小于的话，其实答案上的该位就是初始的“0” 9 y = y - q, ++x.a[i]; //看能减几个除数，减几次，答案上该位就加几次。 10 y.re(); //将数反过来，为下一次添数做准备 11 } 12 x.a[0] = p.a[0]; 13 while (x.a[0] > 0 && !x.a[x.a[0]]) --x.a[0]; 14 return x; 15 }
在struct num里要加这两句
void add(int k) {if(k||a[0]) a[++a[0]]=k;} void re() {reverse(a+1,a+1+a[0]);}