$nlogn$

做法：直接将所有大臣按左右手上的数的乘积从小到大排序，得到的序列就是最优排队方案。

我们记第 $( i$) 个大臣左手上的数是 $( A_i$)，右手上的数是 $( B_i$)。

假设当前的排队方案不是按 $( A_i * B_i$) 从小到大排序的，则一定存在某两个相邻的人，满足 $[ A_i * B_i > A_{i+1} * B_{i+1}$]。

我们现在将这两个人的位置互换，然后考虑他们在交换前和交换后所获得的奖励是多少：

• 交换前：第 $( i$) 个人是 $( \frac{\prod_{j=0}^{i-1} A_j}{B_i}$)，第 $( i+1$) 个人是 $( \frac{\prod_{j=0}^{i} A_j}{B_{i+1}}$)；
• 交换后：第 $( i$) 个人是 $( \frac{\prod_{j=0}^{i-1} A_j}{B_{i+1}}$)，第 $( i+1$) 个人是 $( \frac{A_{i+1}*\prod_{j=0}^{i-1} A_j}{B_i}$)；

由于我们接下来只比较这四个数的大小关系，而且所有 $( A_i, B_i$) 均大于0，所以可以将每个数除以 $( \prod_{j=0}^{i-1} A_j$)，然后乘 $( B_i * B_{i+1}$)，得到：

由于 $( A_i > 0$)，所以 $( B_i \leq A_i * B_i$)，并且 $( A_i * B_i > A_{i+1} * B_{i+1}$)，所以 $[ \max(B_i, A_{i+1} * B_{i+1}) \leq A_i * B_i \leq \max(B_{i+1}, A_i * B_i) $]，所以交换后两个数的最大值不大于交换前两个数的最大值。

而且交换相邻两个数不会对其他人的奖金产生影响，所以如果存在逆序，则将其交换，得到的结果一定不会比原来更差。

大整数(30pts)

#include<bits/stdc++.h>
using namespace std;
const int N=50010;
typedef long long LL;
struct Node{
    LL sum,w,s;
    bool operator<(const Node& W)const
    {
        return sum<W.sum;
    }
}cow[N];
int main()
{
    int n;
    cin>>n;
    n++;
    for(int i=0;i<n;i++)
    {
        cin>>cow[i].w>>cow[i].s;
        cow[i].sum=cow[i].w*cow[i].s;
    }
    sort(cow,cow+n);
    LL res=-2e18;
    LL ss=1;
    for(int i=1;i<n;i++)
    {
    //    cout<<cow[i].w<<" "<<cow[i].s<<endl;
        res=max(res,ss/cow[i].s);
        ss*=cow[i].w;
    }
    cout<<res;
    return 0;
}

大整数模拟

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
const int N=1010,M=4010;
int n;
PII w[N];
bool cmp(PII a,PII b) //按照x*y从小到大排序
{
    if(a.x*a.y<b.x*b.y) return 1;
    return 0;
}
void div(int c[],int a[],int b) //c=a/b;
{
    for(int i=M-1,r=0;i>=0;i--)
    {
        r=r*10+a[i];
        c[i]=r/b;
        r%=b;
    }
}
void mul(int a[],int b) //a=a*b;
{
    for(int i=0,t=0;i<M;i++)
    {
        t+=a[i]*b;
        a[i]=t%10;
        t/=10;
    }
}
int compare(int a[],int b[]) //数组比较大小
{
    for(int i=M-1;i>=0;i--)
    {
        if(a[i]>b[i]) return 1;
        else if(a[i]<b[i]) return -1;
    }
    return 0;
}
void print(int a[]) //高精度输出
{
    int k=M-1;
    while(k&&a[k]==0) k--;
    for(int i=k;i>=0;i--)
    {
        cout<<a[i];
    }
}
int main()
{
    cin>>n;
    for(int i=0;i<=n;i++)
    {
        cin>>w[i].x>>w[i].y;
    }
    sort(w+1,w+1+n,cmp);
    int res[M]={0},p[M]={w[0].x},temp[M]; //初始化
    for(int i=1;i<=n;i++)
    {
        div(temp,p,w[i].y); //计算
        if(compare(res,temp)<0)  //temp更大一些
        {
            memcpy(res,temp,sizeof res);
        }
        mul(p,w[i].x); //累乘
    }
    print(res);
    return 0;
}