国王の游戏

这个国王太会玩了！！

【题意分析】

首先，由于一个大臣所获得的金币数只取决于他右手的金币数，所以前面的大臣顺序并不影响后面大臣的金币数，但会影响自己手中的金币数。然后便想到了贪心。但发现这样子并不能得出最优解。然后经过一番推导，便可以得知一个大臣的左右手乘积越大，就越要放到队伍后面。

然后就开始了玄妙的数学证明时间！！

前方高能！！！

【证明】

…（设这一段乘积为X1）	…（设这一段乘积为Y2）
L1	R1
…（设这一段乘积为X2）	…（设这一段乘积为Y2）
L2	R2

由上面这张表格可以知道这样的情况时：

第一个人所得的金币数为X1/R1；

第二个人所得的金币数为X1×L1×X2/R2；

所以最小值为 max(X1/R1, X1×L1×X2/R2)；

然后交换两个人的位置

…（这一段乘积为X1）	…（这一段乘积为Y2）
L2	R2
…（这一段乘积为X2）	…（这一段乘积为Y2）
L1	R1

由上面这张表格可以知道交换后的情况时：

第一个人所得的金币数为X1×L2×X2/R1；

第二个人所得的金币数为X1/R2；

所以此时最小值为max(X1×L2×X2/R1, X1/R2)；

综合上面两种情况：

如果变换之前的情况要优于变换之后的情况，那么

max(X1/R1, X1×L1×X2/R2) < max(X1×L2×X2/R1, X1/R2);

而X1/R1 < X1×L2×X2/R1 恒成立；

X1×L1×X2/R2 > X1/R2；

所以上述条件成立时

必须有X1×L1×X2/R2 < X1×L2×X2/R1 恒成立；所以化简可得 L1×R1 < L2×R2恒成立。

【正解】

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;

int n, lens = 1, lenm = 1, lena = 1;
int sum[10010] = {0, 1}, maxn[10010] = {0, 1}, ans[10010];

struct tmp
{
    long long l, r;
    bool operator < (const tmp x) const 
    {
            return l * r < x.l * x.r;
    }
}coin[1001];

void muti(long long x)
{
    int tmp = 0;
    for(int i = 1; i <= lens; i++)
        sum[i] *= x;
    for(int i = 1; i <= lens; i++)
    {
        tmp += sum[i];
        sum[i] = tmp %10;
        tmp /= 10;
    }
    while(tmp != 0)
    {
        lens++;
        sum[lens] = tmp % 10;
        tmp /= 10;
    }
}

void cut(long long x)
{
    memset(ans, 0, sizeof(ans));
    lena = lens;
    int tmp = 0;
    for(int i = lena; i >= 1; i--)
    {
        tmp *= 10;
        tmp += sum[i];
        if(tmp >= x)
        {
            ans[i] = tmp / x;
            tmp %= x;
        }
    }
    while(ans[lena] == 0)
    {
        if(lena == 1)
            break;
        lena--;
    }
}

void max()
{
    if(lena > lenm)
    {
        for(int i = 1; i <= lena; i++)
            maxn[i] = ans[i];
        lenm = lena;
    }
    else if(lena == lenm)
    {
        for(int i = lena; i >= 1; i--)
            if(maxn[i] < ans[i])
            {
                for(int j = 1; j <= lena; j++)
                    maxn[j] = ans[j];
                lenm = lena;
                break;
            }
    }
}

int main()
{
//  freopen("game.in", "r", stdin);
//  freopen("game.out", "w", stdout);
    cin >> n;
    cin >> coin[0].l >> coin[0].r;
    for(int i = 1; i <= n; i++)
        scanf("%d %d", &coin[i].l, & coin[i].r);
    sort(coin + 1, coin + n + 1);
    for(int i = 1; i <= n; i++)
    {
        muti(coin[i - 1].l);
        cut(coin[i].r);
        max();
    }
    for(int i = lenm; i >= 1; i--)
        cout << maxn[i];
}

ps:注意数据范围，要使用高精度乘除！！！