题目：链接：https://ac.nowcoder.com/acm/problem/16561
来源：牛客网

恰逢 H 国国庆，国王邀请 n 位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这 n 位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。
国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。
备注：
对于 20%的数据，有 1≤ n≤ 10,0 ＜ a,b ＜ 8 ；
对于 40%的数据，有 1≤ n≤20,0 ＜a,b＜8 ；
对于 60%的数据，有 1≤ n≤100 ；
对于 60%的数据，保证答案不超过 109 ；
对于 100%的数据，有 1 ≤ n ≤1,000,0 ＜ a,b ＜ 10000 。
思路：贪心，公式推导如下
当是···AB···时，A1钱=前面的人左手的乘积的数/A右，B1钱=前面的人左手的乘积的数A左/B右
同理得当···BA···时，B2钱=前面的人左手的乘积的数/B右，A2钱=前面的人左手的乘积的数B左/A右
现在要得钱的人的钱尽量的少那就让max(A1钱，B1钱）小于max（A2钱，B2钱）
因为B左A左>=1，所以A1钱<=A2钱，让A2钱>=B1钱即可让所获得的钱尽量少
得A左A右<=B左B右
按乘积排序然后补上高精度乘除法即可。
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
using namespace std;
struct minister
{
int l;
int r;</string></sstream></algorithm></iostream>

};
string customizemax(string a,string b)//两个字符串的比较
{
if(a.size()>b.size())
{
return a;
}
else
{
if(b.size()>a.size())return b;
else
{
if(a>=b)return a;
else return b;
}
}
}
string multiplication(string a,string b)//高精度乘法
{
int len1=a.size(),len2=b.size();
int c[100000],d[100000];
int i,j;
int ans[10000]= {0};
int maxlen=len1+len2-1,minlen=min(len1,len2);
for(i=0; i<len1; i++)
{
c[i]=a[len1-i-1]-'0';
}
for(i=0; i<len2; i++)
{
d[i]=b[len2-i-1]-'0';
}
int m=0;
int f=0;
for(i=0; i<len1; i++)
{
for(int j=0; j<len2; j++)
{
int t=c[i]d[j];
int x=t/10,y=t%10;
ans[f+j]+=y;
if(ans[f+j]>=10)
{
ans[f+j+1]+=ans[f+j]/10;
ans[f+j]=ans[f+j]%10;
}
ans[f+j+1]+=x;
}
f++;
}
if(ans[maxlen]==0)
{
maxlen--;
}
a.clear();
for(i=0; i<=maxlen; i++)
{
if(ans[maxlen-i]!=0)break;//把前导0都去掉
}
if(i==maxlen+1)a="0";
for(; i<=maxlen; i++)
{
a.push_back(ans[maxlen-i]+'0');
}
return a;
}
int cmp(minister a,minister b)
{
return a.la.r<b.lb.r;
}
string division(string a,int b)//高精度除法
{
int c[100000],d[100000];
int i,len1=a.size();
for(i=0; i<len1; i++)
{
c[i]=a[i]-'0';
}
int m=0,j=0;
for(i=0; i<len1; i++)
{
m+=c[i];
if(m/b!=0)
{
d[j++]=m/b;
m=m%b;
}
else
{
d[j++]=0;
}
m=10;
}
a.clear();
for(i=0; i<j; i++)//把前导0去掉
{
if(d[i]!=0)break;
}
if(i==j)a="0";
for(; i<j; i++)
{
a.push_back(d[i]+'0');
}
return a;
}
string m;
int main()
{
int n;
cin>>n;
minister d[10000]={0};
int a,b;
string m;
cin>>m>>d[0].r;
int i;
string mmax;//存储最大的数字
for(i=1; i<=n; i++)
{
cin>>d[i].l>>d[i].r;
}
sort(d,d+n+1,cmp);//排序。因为数组里包括了国王所以第二个参数要加1
mmax=division(m,d[1].r);
for(i=1; i<=n-1; i++)
{
mmax=customizemax(mmax,division(m,d[i].r));
stringstream st;
st<<d[i].l;
string s;
st>>s;
m=multiplication(m,s);
}
mmax=customizemax(mmax,division(m,d[i].r));
cout<<mmax;
return 0;
}