难度：提高+/省选-

题目描述

        恰逢H国国庆，国王邀请n位大臣来玩一个有奖游戏。首先，他让每个大臣在左，右手上面分别写下一个整数，国王自己也在左，右手上各写一个整数。然后，让这n位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是:排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。
        国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。

输入输出格式

输入格式:

        第一行包含一个整数n，表示大臣的人数。
        第二行包含两个整数 a和b，之间用一个空格隔开，分别表示国王左手和右手上的整数。
        接下来 n行，每行包含两个整数a 和 b，之间用一个空格隔开，分别表示每个大臣左手和右手上的整数。

输出格式:

        一个整数，表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。

输入输出样例

Sample input

3
1 1
2 3
7 4
4 6

Sample output

2

题解

        考察高精度算法和数学推导，难度较大。
        对于两个大臣x，y。假定x前面的大臣左手上数字之积为p(p>0)，那么两者金币数分别为:

        调换位置后，金币数分别为:

        显然有$p*x.l/y.r>p/y.r$且有$p*y.l/x.r>p/x.r$，倘若大臣x在前时金币最大值更小，那么必有$p*x.l/y.r \leq p*y.l/x.r$，即:

        这个不等式是解决本题的关键，它给出了排序的策略。
        易知当大臣站序按照l*r升序时最大值最小，否则必有一组违反上述的不等式，这个时候两人金币最大值会变大，不利于整体最大值尽量小的条件。也就是说，按照该标准排序后，可以保证任何相邻两人的金币最大值尽可能的小，从而整体最大值尽可能小。
        按照该不等式排序，再用高精度算法计算结果并输出即可。
        注意不要重载<=，仅重载<即可获得不降序的结果。重载<=很容易导致RE。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;
int n;
int king_l, king_r;

struct node {
    int l, r;

    bool operator<(node y) {
        if (y.r * y.l > this->l * this->r)return true;
        return false;
    }
} op[1005];

int read() {
    int sum = 0;
    char e;
    e = getchar();
    while (e < '0' || e > '9')e = getchar();
    while (e >= '0' && e <= '9') {
        sum *= 10;
        sum += e - '0';
        e = getchar();
    }
    return sum;
}

bool check(int *p, int *q) {
    if (p[0] < q[0])return true;
    if (p[0] > q[0])return false;
    for (register int i = 1; i <= p[0]; i++) {
        if (p[i] < q[i])return true;
        if (p[i] > q[i])return false;
    }
    return false;
}

void copy(int *p, int *q) {
    p[0] = q[0];
    for (register int i = 1; i <= q[0]; i++)p[i] = q[i];
}

void mutiple(int *p, int q) {
    int r = 0, tp = 0, i;
    for (i = 10000; i > p[0]; i--)tp = p[i], p[i] = (p[i] * q + r) % 10, r = (tp * q + r) / 10;
    while (r > 0)p[i--] = r % 10, r /= 10;
    p[0] = i;
}

void divide(int *x, int y, int *z) {
    int tp = 0, i = x[0] + 1, j = 1;
    while (tp < y)tp *= 10, tp += x[i++];
    while (i <= 10001) {
        z[j++] = tp / y, tp %= y;
        tp *= 10, tp += x[i++];
    }
    z[0] = j - 1;
}

void print(int *x) {
    for (register int i = 1; i <= x[0]; i++)cout << x[i];
    cout << endl;
}

int main() {
    int num[10001] = {0}, temp[10000], ans[10000] = {0};
    num[0] = 9999;
    num[10000] = 1;
    n = read();
    king_l = read(), king_r = read();
    for (register int i = 1; i <= n; i++)op[i].l = read(), op[i].r = read();
    sort(op + 1, op + n + 1);
    mutiple(num, king_l);
    for (register int i = 1; i <= n; i++) {
        divide(num, op[i].r, temp);
        if (check(ans, temp))copy(ans, temp);
        mutiple(num, op[i].l);
    }
    print(ans);
    return 0;
}