【中等】国王游戏

题目

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

注意，国王的位置始终在队伍的最前面。

输入格式

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

输出格式

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

数据范围

{\rm{1}} \le {\rm{n}} \le {\rm{1000}}$``$0<a,b<10000

输入样例：

3
1 1
2 3
7 4
4 6

输出样例：

2

题解

算法

(贪心) {\rm{O(}}{{\rm{n}}^{\rm{2}}}{\rm{)}} 我们先给出做法，再证明其正确性。

做法：直接将所有大臣按左右手上的数的乘积从小到大排序，得到的序列就是最优排队方案。

证明：

我们记第 i 个大臣左手上的数是 {{\rm{A}}_i} ，右手上的数是 {{\rm{B}}_i} 。假设当前的排队方案不是按 {A_i}*{B_i} 从小到大排序的，则一定存在某两个相邻的人，满足 {A_i}*{B_i} > {A_{i + 1}}*{B_{i + 1}}

• 交换前：第 i 个人是 \frac{{\Pi _{j = 0}^{i - 1}{A_j}}}{{{B_i}}} ，第 {\rm{i + 1}} 个人是 \frac{{\Pi _{j = 0}^i{A_j}}}{{{B_{i + 1}}}} ;
• 交换后：第 i 个人是 \frac{{\Pi _{j = 0}^{i - 1}{A_j}}}{{{B_{i + 1}}}} ，第 i+1 个人是 \frac{{{A_{i + 1}}*\Pi _{j = 0}^{i - 1}{A_j}}}{{{B_i}}} ;

由于我们接下来只比较这四个数的大小关系，而且所有 {A_i},{B_i} 均大于 0，所以可以将每个数除以 \prod\nolimits_{j = 0}^{i - 1} {{A_j}} ，然后乘 {B_i}*{B_{i + 1}} ，得到：

由于 {A_i} > 0$``$B_{i} \leq A_{i} * B_{i} ，并且A_{i} * B_{i}>A_{i+1} * B_{i+1}$``$\max \left(B_{i}, A_{i+1} * B_{i+1}\right) \leq A_{i} * B_{i} \leq \max \left(B_{i+1}, A_{i} * B_{i}\right) , 所以交换后两个数的最大值不大于交换前两个数的最大值。而且交换相邻两个数不会对其他人的奖金产生影响，所以如果存在逆序，则将其交换，得到的结果一定不会比原来更差。

所以从小到大排好序的序列就是最优解，证毕。

时间复杂度

排序的时间复杂度是 O(nlogn) 。这道题目的时间复杂度瓶颈在高精度计算上，最坏情况下所有 A_{i}=9999 ，则前 i 个数的乘积大约是 {\rm{4i}} 位，每次乘一个新的数就需要 {\rm{4i}} 的计算量，所以总共的计算量是 O\left(4 * \sum_{i=1}^{n} i\right)=O\left(n^{2}\right) 。

C++ 代码

#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef pair<int, int> PII;
const int N = 1010;

int n;
PII p[N];

vector<int> mul(vector<int>a, int b)
{
    vector<int> c;
    int t = 0;
    for (int i = 0; i < a.size(); i ++ )
    {
        t += a[i] * b;
        c.push_back(t % 10);
        t /= 10;
    }
    while (t)
    {
        c.push_back(t % 10);
        t /= 10;
    }
    return c;
}

vector<int> div(vector<int>a, int b)
{
    vector<int> c;
    bool is_first = true;
    for (int i = a.size() - 1, t = 0; i >= 0; i -- )
    {
        t = t * 10 + a[i];
        int x = t / b;
        if (!is_first || x)
        {
            is_first = false;
            c.push_back(x);
        }
        t %= b;
    }
    reverse(c.begin(), c.end());
    return c;
}

vector<int> max_vec(vector<int> a, vector<int> b)
{
    if (a.size() > b.size()) return a;
    if (a.size() < b.size()) return b;
    if (vector<int>(a.rbegin(), a.rend()) > vector<int>(b.rbegin(), b.rend())) return a;
    return b;
}

int main()
{
    cin >> n;
    for (int i = 0; i <= n; i ++ )
    {
        int a, b;
        cin >> a >> b;
        p[i] = {a * b, a};
    }
    sort(p + 1, p + n + 1);

    vector<int> product(1, 1);

    vector<int> res(1, 0);
    for (int i = 0; i <= n; i ++ )
    {
        if (i) res = max_vec(res, div(product, p[i].first / p[i].second));
        product = mul(product, p[i].second);
    }

    for (int i = res.size() - 1; i >= 0; i -- ) cout << res[i];
    cout << endl;

    return 0;
}

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。

​