恰逢 H 国国庆,国王邀请 n 位大臣来玩一个有奖游戏.首先,他让每个大臣在左、右 手上面分别写下一个整数,国王自己也在左、右手上各写一个整数.然后,让这 n 位大臣排 成一排,国王站在队伍的最前面.排好队后,所有的大臣都会获得国王奖赏的若干金币,每 位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右 手上的数,然后向下取整得到的结果.
国王不希望某一个大臣获得特别多的奖赏,所以他想请你帮他重新安排一下队伍的顺序,使得获得奖赏最多的大臣,所获奖赏尽可能的少.注意,国王的位置始终在队伍的最前面.
【输入】
输入文件为 game.in.
第一行包含一个整数 n,表示大臣的人数.
第二行包含两个整数 a 和 b,之间用一个空格隔开,分别表示国王左手和右手上的整数.接下来 n 行,每行包含两个整数 a 和 b,之间用一个空格隔开,分别表示每个大臣左手
和右手上的整数.
【输出】
输出文件名为 game.out.输出只有一行,包含一个整数,表示重新排列后的队伍中获奖赏最多的大臣所获得的
金币数.
【输入输出样例】
game.in
game.out
3
1 1
2 3
7 4
4 6
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.
【数据范围】
对于 20%的数据,有 1≤ n≤ 10,0 < a、b < 8；
对于 40%的数据,有 1≤ n≤20,0 < a、b < 8； 对于 60%的数据,有 1≤ n≤100；
对于 60%的数据,保证答案不超过 10的九次方；
对于 100%的数据,有 1 ≤ n ≤1,000,0 < a、b < 10000.
考试的时候用的贪心【并且没加高精度(╯‵□′)╯︵┻━┻于是只有四十分，思路不是很清晰
考完了老师解释了一下这道题的选择策略：最优的大臣排队顺序是按他们左手与右手的乘积从低到高排序，即乘积小的在前，乘积大的在后
策略解释如下；
国王的左手值为L，右手值为R；
假定两个大臣，A大臣左手值为A，右手值为a；B大臣左手值为B,右手值为b。
如果排序为AB，那么两大臣的金币数分别为L/a，L*A/b；
如果排序为BA，那么两大臣的金币数分别为L/b，L*B/a；
最终答案比较L*A/b和L*B/a，约去L后我们实际比较的是A*a和B*b，且乘积大的数放在后面能使最大值最小；
然后加高精度就行了【因为有高精的原因，代码略长】。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n;
struct node{
int num;
int right,left;
int sum;
}e[];
int ans[];
int l_ans=;
bool cmp(node e1,node e2)
{
return e1.sum>e2.sum;
}
void read()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d%d",&e[i].left,&e[i].right);
e[i].sum=e[i].left*e[i].right;
}
sort(e+,e+n+,cmp);//排序乘积；
}
void cheng(int x)//高精乘
{
int b[];
int l=;
b[l]=x%;
while(x>=)
{
l++;
b[l]=x%;
x=x/;
}//将乘数转换到数组内；
for(int i=;i<=l;i++)
{
if(ans[i]>=){
ans[i+]+=ans[i]/;
ans[i]=ans[i]%;
}//进位；
ans[i]*=b[i];
if(ans[i]>=){
ans[i+]+=ans[i]/;
ans[i]=ans[i]%;
}//进位；
}
l++;
if(ans[l]>=)
{
ans[l+]+=ans[l]/;
ans[l]=ans[l]%;
l++;
}//最高位进位；
l_ans=max(l_ans,l-);//记录答案长度；
}
void work()
{
int a=;
while(e[].left>=)
{
a++;
ans[a]=e[].left%;
e[].left=e[].left/;
}
ans[a+]=e[].left;//国王的左手值为初始值；
for(int i=;i<=n;i++)
{
cheng(e[i].left);
}
int b=l_ans;
while(ans[b]!=)
{
ans[b-]+=ans[b]%e[].right*;
ans[b]=ans[b]/e[].right;
b--;
}//高精除以低精；
while(l_ans!=) //去除高位的0；
{
if(ans[l_ans]!=)
{
for(int i=l_ans;i>=;i--)
{
printf("%d",ans[l_ans]);
}r
return;
}
l_ans--;
}
}
int main()
{
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
read();
work();
return ;
}