P1080 [NOIP2012 提高组] 国王游戏
题目
恰逢 H 国国庆，国王邀请 \(n\) 位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这 \(n\) 位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。
国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。
输入
第一行包含一个整数 \(n\)，表示大臣的人数。
第二行包含两个整数 \(a\) 和 \(b\)，之间用一个空格隔开，分别表示国王左手和右手上的整数。
接下来 \(n\) 行，每行包含两个整数 \(a\) 和 \(b\)，之间用一个空格隔开，分别表示每个大臣左手和右手上的整数。
输出
一个整数，表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。
样例
输入
3
1 1
2 3
7 4
4 6
输出
2
提示
【输入输出样例说明】
按 \(1\)、\(2\)、\(3\) 这样排列队伍，获得奖赏最多的大臣所获得金币数为 \(2\)；
按 \(1\)、\(3\)、\(2\) 这样排列队伍，获得奖赏最多的大臣所获得金币数为 \(2\)；
按 \(2\)、\(1\)、\(3\) 这样排列队伍，获得奖赏最多的大臣所获得金币数为 \(2\)；
按$ 2$、\(3\)、$1 $这样排列队伍，获得奖赏最多的大臣所获得金币数为 \(9\)；
按 \(3\)、\(1\)、$2 $这样排列队伍，获得奖赏最多的大臣所获得金币数为 \(2\)；
按$ 3$、\(2\)、\(1\) 这样排列队伍，获得奖赏最多的大臣所获得金币数为 \(9\)。
因此，奖赏最多的大臣最少获得 \(2\) 个金币，答案输出 \(2\)。
【数据范围】
对于 \(20\%\) 的数据，有 \(1≤ n≤ 10,0 < a,b < 8\)；
对于 \(40\%\) 的数据，有$ 1≤ n≤20,0 < a,b < 8$；
对于 \(60\%\) 的数据，有 \(1≤ n≤100\)；
对于 \(60\%\) 的数据，保证答案不超过 \(10^9\)；
对于 \(100\%\) 的数据，有 \(1 ≤ n ≤1,000,0 < a,b < 10000\)。
思路
对于国王身后的两个大臣进行分析，第一种情况：
| 左 | 右 | |
|---|---|---|
| 国王 | \(a_0\) | \(b_0\) |
| \(p_1\) | \(a_1\) | \(b_1\) |
| \(p_2\) | \(a_2\) | \(b_2\) |
第一种情况答案为 \(\max(a_0/b_1,(a_0 \times a_1)/b _ 2)\)。
\(p_1,p_2\) 换一下位置，第二种情况：
| 左 | 右 | |
|---|---|---|
| 国王 | \(a_0\) | \(b_0\) |
| \(p_1\) | \(a_2\) | \(b_2\) |
| \(p_2\) | \(a_1\) | \(b_1\) |
第二种情况答案为 \(\max(a_0/b_2,(a_0 \times a_2)/b_1)\)。
比较
\[a_0/b_1,(a_0 \times a_1)/b_2,a_0/b_2,(a_0 \times a_2)/b_1 \]这四项，其中
\[(a_0 \times a_1)/b_2>a_0/b_2,(a_0 \times a_2)/b_1>a_0/b_1 \]那么问题转换为比较
\[(a_0 \times a_1)/b_2 \]\[(a_0 \times a_2)/b_1 \]这两项的值。如果 \(p_1\) 排在前面答案更大，就说明
\[(a_0 \times a_1)/b_2>(a_0 \times a_2)/b_1 \]即
\[a_1 \times b_1>a_2 \times b_2 \]同理如果 \(p_2\) 排在前面答案更大，就说明
\[a_1 \times b_1<a_2 \times b_2 \]所以为了使答案取到最小值，我们需要将 \(a_i \times b_i\) 较小的放在前面，那么以 \(a_i \times b_i\) 为关键字排序即可。之后依次比较当前大臣前面的所有人左手上的数的乘积除以他自己右手上的数，并向下取整得到的结果，取最大值。由于 \(1 \le n \le 1000,0<a,b<10000\)，左手上的数的乘积最大值为 \(10000^{10}=(10^4)^{10}\)，结果达到 \(4000\) 位，远远超过 \(\operatorname{long long}\) 范围，因此需要使用高精度运算。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 4005;
struct Node
{
int l, r;
Node() // 结构体初始化
{
}
Node(int x, int y) : l(x), r(y) // 结构体初始化
{
}
bool operator < (const Node &x) const
{
return l * r < x.l * x.r;
}
} a[N];
struct Data
{
int s[N], len;
Data() // 初始化
{
memset(s, 0, sizeof(s));
len = 1;
}
Data(int x) // 初始化
{
memset(s, 0, sizeof(s));
len = 1;
int i = 0;
while (x)
{
s[++ i] = x % 10;
x /= 10;
}
len = i;
}
} ans;
Data operator * (const Data &a, const int &b) // 高精度 * 单精度
{
Data c;
c.len = a.len;
for (int i = 1; i <= c.len; i ++ )
{
c.s[i] += a.s[i] * b;
c.s[i + 1] += c.s[i] / 10;
c.s[i] = c.s[i] % 10;
}
if (c.s[c.len + 1])
{
int x = c.s[c.len + 1], len = c.len;
while (x)
{
c.s[++ len] = x % 10;
x /= 10;
}
c.len = len;
}
return c;
}
Data operator / (const Data &a, const int &b) // 高精度除以低精度
{
Data c;
c.len = a.len;
int x = 0;
for (int i = c.len; i >= 1; i -- )
{
x = x * 10 + a.s[i];
c.s[i] = x / b;
x %= b;
}
while (!c.s[c.len] && c.len > 1)
c.len --; // 去掉前导零
return c;
}
bool operator < (const Data &a, const Data &b) // 重载 < 号
{
if (a.len == b.len)
{
int i;
for (i = a.len; a.s[i] == b.s[i] && i > 1; i -- );
if (i >= 1)
return a.s[i] < b.s[i];
else
return 0;
}
else
return a.len < b.len;
}
void print(const Data &a)
{
for (int i = a.len; i >= 1; i -- )
printf("%d", a.s[i]);
}
int n, x, y;
int main()
{
scanf("%d", &n);
for (int i = 0; i <= n; i ++ )
{
scanf("%d %d", &x, &y);
a[i] = Node(x, y);
}
sort(a + 1, a + n + 1);
Data k(1);
for (int i = 1; i <= n; i ++ )
{
if (a[i - 1].l == 0) // 判 0
break;
k = k * a[i - 1].l;
Data temp; // 注意被除数用 temp 存下来
temp = k / a[i].r;
if (ans < temp)
ans = temp;
}
print(ans);
return 0;
}