https://www.luogu.org/problemnew/show/P1080

这道题要获奖赏最多的大臣所获奖赏尽量低，但是是不能二分的，因为不能根据一个最多获奖赏数额来确定最优排序。

考虑一个已经排好序的序列，看第i-1和i个大臣，设前i-2个大臣的左手之积是x，第i-1个大臣左ai-1，右bi-1，第i个大臣左ai，右bi。

不管他俩换不换，对于序列这两人之前以及之后没有任何影响。

如果这两人不换位置，这两人最高奖赏是max{①x/b[i-1],②x*a[i-1]/b[i]}，如果换，则是max{③x/b[i],④x*a[i]/b[i-1]}

一定有①<④，③<②。

若换前的max大于换后的max，则换了对于最终答案可能好，可能没影响，有变好的趋势，至少不会变差。

若换前的max小于换后的max，则不换。

根据这两个max个进行sort()完成后，对于任意响邻两个人，都不换为好，于是就ok了。

（看题解，只需以a*b为关键字升序排序就可以了，因为不换等价于④>②，换等价于④<②，④==②的话一样）

这题还要高精度，高精和普通的乘除都O(n),乘上n最大取10^4,最后运算应该是要大于10^8的，交上去感觉要超时，结果没有，而且还挺快的，不知道为什么，看来对时间复杂度分析很不过关。

#include<bits/stdc++.h>
using namespace std;

int n;
string ans,sum;
struct Man{
	int a, b;
}man[10005];

bool cmp(Man x,Man y)
{
	return max(1.0/x.b,x.a*1.0/y.b)<max(1.0/y.b,y.a*1.0/x.b);
}

const int L=10005;
int na[L];
string mul(string a,int b)//高精度a乘单精度b
{
    string ans;
    int La=a.size();
    fill(na,na+L,0);
    for(int i=La-1;i>=0;i--) na[La-i-1]=a[i]-'0';
    for(int i=0;i<La;i++) na[i]=na[i]*b;    
    int pos;
    for(pos=0;pos<La-1;pos++)na[pos+1]+=na[pos]/10,na[pos]%=10;
    while(na[pos])na[pos+1]=na[pos]/10,na[pos]%=10,pos++;
    while((!na[--pos])&&pos)continue; 
    pos++;
    for(int i=pos-1;i>=0;i--)ans+=na[i]+'0';
    return ans;
}

string div(string a,int b)//高精度a除以单精度b
{
    string r,ans;
    int d=0;
    if(a=="0") return a;//特判
    for(int i=0;i<a.size();i++)
    {
            r+=(d*10+a[i]-'0')/b+'0';//求出商
            d=(d*10+(a[i]-'0'))%b;//求出余数
    }
  //此时d就是a%b 
    int p=0;
    for(int i=0;i<r.size();i++)
    if(r[i]!='0') {p=i;break;}
    if(p==0&&r[p]=='0')p=r.size()-1;
    return r.substr(p);
}

string maxx(string a,string b)
{
	if(a.length()!=b.length())return a.length()>b.length()?a:b;
	return max(a,b);
}

void calc()
{
	ans="0";
	sum=mul("1",man[0].a);
	for(int i=1;i<=n;i++)
	{
		ans=maxx(ans,div(sum,man[i].b));
		sum=mul(sum,man[i].a);
	}
}

int main()
{
	freopen("input.in","r",stdin);
	cin>>n;
	for(int i=0;i<=n;i++)cin>>man[i].a>>man[i].b;
	sort(man+1,man+1+n,cmp);
	calc();
	cout<<ans<<endl;
	
	return 0;
}