原题：
恰逢 H 国国庆，国王邀请 n 位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这 n 位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。
国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。
输入输出格式
输入格式：
第一行包含一个整数 n，表示大臣的人数。
第二行包含两个整数 a和 b，之间用一个空格隔开，分别表示国王左手和右手上的整数。
接下来 n 行，每行包含两个整数 a 和 b，之间用一个空格隔开，分别表示每个大臣左手和右手上的整数。
输出格式：
一个整数，表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。
输入输出样例
输入样例#1：
3
1 1
2 3
7 4
4 6
输出样例#1：
2
说明
【输入输出样例说明】
按 1、2、3 这样排列队伍，获得奖赏最多的大臣所获得金币数为 2；
按 1、3、2 这样排列队伍，获得奖赏最多的大臣所获得金币数为 2；
按 2、1、3 这样排列队伍，获得奖赏最多的大臣所获得金币数为 2；
按 2、3、1这样排列队伍，获得奖赏最多的大臣所获得金币数为 9；
按 3、1、2这样排列队伍，获得奖赏最多的大臣所获得金币数为 2；
按 3、2、1这样排列队伍，获得奖赏最多的大臣所获得金币数为 9。
因此，奖赏最多的大臣最少获得 2 个金币，答案输出 2。
【数据范围】
1≤n≤1,000 , 0<a,b<10000。
题意:
有一个国王和n个大臣，每个人左右手上都有数字ai和bi，规则是国王永远排在第一个，其余大臣紧随其后，每一个大臣都能够得到国王的奖赏，奖赏的金额就是在本人前面所排的所有大臣的左手中的数字之积除以本人的右手数字。现在为了使最大奖赏金额最低，由你来排序，最终输出最高奖赏金额的最小值。
题解：
这道题目由两个知识点组成，一个是贪心，另一个是高精度。
贪心方面：
我们只需要将aixbi作为关键值比较，由小到大排序即可。下面验证一下贪心算法的正确性：
以aixbi排序，就只拿两个人之间来比较，（假设两个人左右手分别为a1，b1，a2，b2，且a1xb1<a
2xb2).若是aixbi小的排在前面则两位大臣分别能得到s（此人之前的大臣的左手乘积）/b1（记为k1），和（a1xs）/b2（记为k2）.
若是aixbi较大的排在前面则两位大臣分别能得到s/b2（记为k3）和（a2xs）/b1（记为k4），这四个奖赏金额中k4>k1，k2>k3,所以最大值只能在k3和k4中选择，而由于a1xb1<a2xb2,由此不等式将k4中的a2替换掉，则能够得到k4>k3,所以只有当aixbi小的排在前面才有可能使最大金额降低。
那么为什么只用验证在两个人之间成立就能推及所有成立呢?
因为对于这两个人以后的人，影响到他们获得奖赏金额的只有两个人左手数字之积，无论两个人怎么排序都不会影响到后边的人。
那么最终输出答案应该是什么呢?
因为你这样排序后面的人得到的比之前的人多，所以最终答案就是最后一个人得到的赏金。
高精度方面：
这也是这道题的坑人之处吧，很多人在这道题目上只先去想应该怎么解决，而没有注意到数据范围（1000个10000相乘，是10^4000次方）这么大的数据就只能够用数组来储存了。高精度乘除法，就是乘法从最低位开始，除法从最高位开始就可以了。
附上AC代码：
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int n,g[1000005],l=1;//g[]数组用来储存高精度乘积，l来记录数组的长度
struct per
{
int a,b;
}st[10005];//每一个人的左右手数字
bool cmp(per aa,per bb)
{
int x=aa.a*aa.b;
int y=bb.a*bb.b;
return x<y;
}//以ai*bi作为关键值排序
void gj1(int x)//高精度乘法
{
for(int i=1;i<=l;++i)g[i]*=st[x].a;//从低位开始乘
for(int i=1;i<=l;i++)
{
g[i+1]+=(g[i]/10);//对于每一位都除掉10得到的数字就是该向上进位的值
g[i]=g[i]%10;//该元素本身保留余10的结果
}
l++;//数组长度要加一，即使最高一位没有进位，先加上也无妨，在之后也会把多加的长度去掉
while(g[l]>9)//对于最高一位再向上进位，变成十进制
{
g[l+1]+=(g[l]/10);
g[l]=g[l]%10;
l++;
}
if(g[l]==0)l--;//如果数组前面是0，则数组长度减一
}
void gj2()
{
for(int i=l;i>=1;i--)//从高位开始
{
g[i-1]+=((g[i]%st[n].b)*10);//除不尽的小数部分（余数），向低位*10相加
g[i]/=st[n].b;//本身保留除后的整数部分
}
while(g[l]==0)l--;//如果数组首位是0，数组长度减一，因为不用输出0
if(l==0)//但是如果最终数组长度为0，又由于每个人都会得到赏金，所以每个人最多只能分到1赏金
cout<<1<<endl;
}
int main()
{
cin>>n;
for(int i=0;i<=n;++i)
{
cin>>st[i].a>>st[i].b;
}
sort(st+1,st+n+1,cmp);
//for(int i=0;i<=n;++i)cout<<st[i].a<<" "<<st[i].b<<endl;
g[1]=st[0].a;//初始化
for(int i=1;i<n;i++)gj1(i);
gj2();
for(int i=l;i>=1;i--)cout<<g[i];//从首位输出
cout<<endl;
return 0;
}
欢迎评论！