考虑大臣 $k, k + 1$ 交换。
原先 $k$ 的奖励为 $\prod\limits_{i = 0}^{k - 1} a_i \cdot \dfrac{1}{b_k}$,$k + 1$ 的奖励为 $\prod\limits_{i = 0}^{k} a_i \cdot \dfrac{1}{b_{k + 1}}$。
原先位置为 $k$ 交换后的奖励为 $\prod\limits_{i = 0}^{k - 1}a_i \cdot \dfrac{a_{k + 1}}{b_k}$, 原先位置为 $k + 1$ 交换后的的奖励为 $\prod\limits_{i = 0}^{k - 1} a_i \cdot \dfrac{1}{b_{k + 1}}$。
我们考虑 $2$ 种操作哪种最优 。
因为其他的大臣的奖励都没有改变,所以我们只需比较以上两组式子的最大值变化:提取公因式 $\prod\limits_{i = 0} ^ {k - 1} a_i$ 之后,相当于只要比较 $\max(\dfrac{1}{b_k}, \dfrac{a_k}{b_{k + 1}})$ 和 $\max(\dfrac{a_{k + 1}}{b_k},\dfrac{1}{b_{k + 1}})$ 的大小关系。考虑两边同时乘以 $b_k \cdot b_{k + 1}$,即比较 $\max(b_{k + 1}, a_k \cdot b_k)$ 和 $\max(a_{k + 1} \cdot b_{k + 1}, b_k)$ 的大小关系。因为任意的 $a_i$ 和 $b_i$ 都是正整数,所以 $a_k \cdot b_k > a_k$,$a_{k + 1} \cdot b_{k + 1} > a_{k + 1}$。故我们只需要比较 $a_k \cdot b_k$ 和 $a_{k + 1} \cdot b_{k + 1}$ 的大小关系。 若 $a_k \cdot b_k < a_{k + 1} \cdot b_{k + 1}$ 则更换前更优,否则更换后更优,也就是说,我们只需要将 $a_i \cdot b_i$ 作为排序关键字,这样得到的序列便是最优解。
$Code:$
#include <bits/stdc++.h>
#define lep(i, r, l) for (int i = r; i >= l; -- i)
#define rep(i, l, r) for (int i = l; i <= r; ++ i)
const int MaxN = 1e4 + 10;
using namespace std;
inline int read() {
int cnt = 0, opt = 1; char ch = getchar();
for (; ! isdigit(ch); ch = getchar())
if (ch == '-') opt = 0;
for (; isdigit(ch); ch = getchar())
cnt = (cnt << 3) + (cnt << 1) + (ch ^ 48);
return opt ? cnt : -cnt;
}
struct num {
int len, s[MaxN];
num (int a = 0) {
len = 0;
memset(s, 0, sizeof(s));
while (a) {
s[++ len] = a % 10;
a /= 10;
}
}
num operator * (const num &a) const {
num c;
int x;
rep (i, 1, a.len) {
x = 0;
rep (j, 1, len) {
c.s[i + j - 1] += a.s[i] * s[j] + x;
x = c.s[i + j - 1] / 10;
c.s[i + j - 1] %= 10;
}
c.s[i + len] = x;
}
c.len = a.len + len;
while (! c.s[c.len] && c.len != 1) c.len --;
return c;
}
num operator / (const int &a) const {
num c;
int x = 0;
c.len = len;
lep (i, c.len, 1) {
x = x * 10 + s[i];
c.s[i] = x / a;
x %= a;
}
while (! c.s[c.len] && c.len != 1) c.len --;
return c;
}
bool operator < (const num &x) const {
if (len != x.len)
return len < x.len;
lep (i, len, 1)
if (s[i] != x.s[i])
return s[i] < x.s[i];
return 0;
}
};
struct king {
int l, r;
} finger[MaxN];
inline int cmp(king x, king y) {
return x.l * x.r < y.l * y.r;
}
int n;
num res, ans;
int main() {
n = read();
finger[0].l = read(), finger[0].r = read();
rep (i, 1, n)
finger[i].l = read(), finger[i].r = read();
stable_sort(finger + 1, finger + 1 + n, cmp);
res = finger[0].l;
rep (i, 1, n) {
if (ans < res / finger[i].r)
ans = res / finger[i].r;
res = res * finger[i].l;
}
lep (i, ans.len, 1) cout << ans.s[i];
return 0;
}
我的个乖乖!都写这么高深吗!STO STO STO STO STO STO STO STO STO
Orz
orz