题解：P1080 [NOIP2012 提高组] 国王游戏

VitrelosTia · 2025-01-12 21:38:54 · 题解

看到任意排列想到邻项交换贪心，发现交换两个相邻并不会造成其他影响，而对于相邻两人而言，肯定是他们两者的最大值越小越好，于是可以直接假设相邻两项 (a_x, b_x)，(a_y, b_y)，前面的 \prod a = k，那么 x 排在 y 的条件是 \dfrac{ka_x}{b_y} < \dfrac{ka_y}{b_x}，把 k 除掉并去分母可得 a_xb_x<a_yb_y，直接按这个排序即可。要高精度，让豆包帮你把 c++ 翻译成 python 即可。

// 不可通过的

#include <bits/stdc++.h>
using namespace std;

const int N = 1005;
int n; struct Node { int a, b; } o[N];

signed main() {
    cin >> n;
    for (int i = 0; i <= n; i++) cin >> o[i].a >> o[i].b;
    sort(o + 1, o + n + 1, [](Node x, Node y) { return x.a * x.b < y.a * y.b; });
    int ans = 0, pre = o[0].a;
    for (int i = 1; i <= n; i++) {
        ans = max(ans, pre / o[i].b);
        pre *= o[i].a;
    }
    cout << ans;
    return 0;
}

# 可通过的，大体是豆包写的，改了一点

n = int(input())
o = []
for i in range(0, n + 1):
    a, b = map(int, input().split())
    o.append((a, b))
o[1:] = sorted(o[1:], key=lambda x: x[0] * x[1])
ans = 0
pre = o[0][0]
for i in range(1, n + 1):
    ans = max(ans, pre // o[i][1])
    pre *= o[i][0]
print(ans)