推那个贪心直接自己推就好了，最后推出来最优解在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("\n");
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]);}