PEEK123 [P1080] 国王游戏(简化版)

题目链接

PEEK123 [P1080] 国王游戏(简化版)

题目描述

国王和 位大臣玩游戏。国王的左右手分别写有整数 ，第 位大臣左右手分别写有 。

所有大臣排成一队，国王站在最前面。对于排在第 个位置的大臣，他能获得的金币数是 。也就是说，金币数等于国王和他前面所有大臣的左手数字的乘积，再除以他自己右手上的数字。

国王希望通过调整大臣的站位顺序，使得获得金币数最多的大臣得到的金币数尽可能小。请求出这个最小的最大金币数。

解题思路

这是一个典型的最小化最大值问题，通常可以通过贪心算法找到最优解。问题的关键是确定大臣们的最佳排序策略。

我们可以通过“微扰/邻项交换”的思想来推导排序的准则。假设在当前队列中，有两个相邻的大臣 和 （ 在 前面）。我们来分析交换他们的位置对结果的影响。

设国王和他们前面的大臣左手数字的累乘积为 。

  1. 顺序为 时：

    • 大臣 的奖励为
    • 大臣 的奖励为
    • 此时，这两位大臣以及他们之后所有大臣中，奖励的最大值主要由 决定（因为分母不变，分子在累积）。所以我们关注这两个位置产生的最大奖励，即 。

  2. 顺序为 时：

    • 大臣 的奖励为
    • 大臣 的奖励为
    • 这两个位置产生的最大奖励为 。

交换 的位置，对他们之前和之后的大臣的奖励没有影响（对于之后的大臣，分子同样是累乘 ）。因此，要使全局的最大奖励最小，我们必须保证任意相邻两项的安排都是最优的。

我们希望顺序 比 更优，这意味着由 产生的局部最大奖励应该小于等于由 产生的局部最大奖励：

忽略取整符号（它不影响大小关系）和公共因子 ：

为了方便比较，两边同时乘以 （）：

现在我们来证明，如果 ，那么上述不等式恒成立。

证明：

假设 。我们需要证明 。

我们使用反证法。假设该不等式不成立，即 。

因为 ，所以要使左边大于右边，必须有 。

这导出两个不等式：

从 可以推出 。但这与题目中 为正整数的条件相矛盾。 因此假设不成立，原不等式成立。

结论：当 时，将大臣 排在 前面会得到不劣于交换后的解。因此，我们的贪心策略就是将所有大臣按照 的值从小到大进行排序。

高精度计算

由于大臣左手数字的累乘积 会非常大，会超出 long long 的表示范围，所以需要使用高精度计算。Python 原生支持大整数，Java 有 BigInteger 类，C++ 则需要手动实现或使用第三方库。

算法步骤：

  1. 读入国王和所有大臣的数据。
  2. 将 位大臣按照 的乘积进行升序排序。
  3. 初始化累乘积 product 为国王的 。
  4. 初始化最大奖励 max_reward 为 0。
  5. 遍历排序后的大臣列表： a. 计算当前大臣的奖励： reward = product / b_i。 b. 更新 max_reward = max(max_reward, reward)。 c. 更新累乘积：product = product * a_i。
  6. 输出 max_reward。

代码

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

// 高精度数结构体
struct BigInt {
    string digits;

    BigInt(long long n = 0) : digits(to_string(n)) {}
    BigInt(string s) : digits(s) {
        if (digits.empty()) digits = "0";
    }
};

// 比较两个高精度数
bool operator<(const BigInt& a, const BigInt& b) {
    if (a.digits.length() != b.digits.length()) {
        return a.digits.length() < b.digits.length();
    }
    return a.digits < b.digits;
}

// 高精度数乘以int
BigInt operator*(const BigInt& a, int b) {
    if (a.digits == "0" || b == 0) return BigInt(0);
    string res = "";
    int carry = 0;
    for (int i = a.digits.length() - 1; i >= 0; --i) {
        carry += (a.digits[i] - '0') * b;
        res += to_string(carry % 10);
        carry /= 10;
    }
    if (carry) res += to_string(carry);
    reverse(res.begin(), res.end());
    return BigInt(res);
}

// 高精度数除以int
BigInt operator/(const BigInt& a, int b) {
    string res = "";
    long long rem = 0;
    for (char digit : a.digits) {
        rem = rem * 10 + (digit - '0');
        res += to_string(rem / b);
        rem %= b;
    }
    size_t first_digit = res.find_first_not_of('0');
    if (string::npos != first_digit) {
        return BigInt(res.substr(first_digit));
    }
    return BigInt(0);
}

struct Minister {
    int id;
    long long a, b;
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    long long king_a, king_b;
    cin >> king_a >> king_b;

    vector<Minister> ministers(n);
    for (int i = 0; i < n; ++i) {
        ministers[i].id = i;
        cin >> ministers[i].a >> ministers[i].b;
    }

    sort(ministers.begin(), ministers.end(), [](const Minister& m1, const Minister& m2) {
        return m1.a * m1.b < m2.a * m2.b;
    });

    BigInt product(king_a);
    BigInt max_reward(0);

    for (int i = 0; i < n; ++i) {
        BigInt current_reward = product / ministers[i].b;
        if (max_reward < current_reward) {
            max_reward = current_reward;
        }
        product = product * ministers[i].a;
    }

    cout << max_reward.digits << '\n';

    return 0;
}

import java.util.Scanner;
import java.util.Arrays;
import java.math.BigInteger;

class Minister implements Comparable<Minister> {
    long a, b;

    public Minister(long a, long b) {
        this.a = a;
        this.b = b;
    }

    @Override
    public int compareTo(Minister other) {
        return Long.compare(this.a * this.b, other.a * other.b);
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        long kingA = sc.nextLong();
        long kingB = sc.nextLong(); // kingB is unused

        Minister[] ministers = new Minister[n];
        for (int i = 0; i < n; i++) {
            ministers[i] = new Minister(sc.nextLong(), sc.nextLong());
        }

        Arrays.sort(ministers);

        BigInteger product = BigInteger.valueOf(kingA);
        BigInteger maxReward = BigInteger.ZERO;

        for (int i = 0; i < n; i++) {
            BigInteger currentReward = product.divide(BigInteger.valueOf(ministers[i].b));
            if (maxReward.compareTo(currentReward) < 0) {
                maxReward = currentReward;
            }
            product = product.multiply(BigInteger.valueOf(ministers[i].a));
        }

        System.out.println(maxReward);
    }
}

import sys

def main():
    n = int(input())
    king_a, king_b = map(int, input().split())
    
    ministers = []
    for _ in range(n):
        a, b = map(int, input().split())
        ministers.append((a, b))
        
    # 根据 a * b 的乘积进行升序排序
    ministers.sort(key=lambda x: x[0] * x[1])
    
    product = king_a
    max_reward = 0
    
    for a, b in ministers:
        reward = product // b
        if reward > max_reward:
            max_reward = reward
        product *= a
        
    print(max_reward)

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法：贪心算法 + 高精度计算。
  • 时间复杂度：主要瓶颈在于排序和高精度运算。
    • 排序的时间复杂度是 。
    • 循环中进行 次高精度乘法和除法。累乘积的位数最多可达 。每次高精度运算的时间与数的位数成正比。因此，循环部分的总复杂度较高，但对于本题数据范围是可以通过的。
  • 空间复杂度：，用于存储大臣信息。高精度数本身也需要与位数成正比的空间。