NC16561 国王的游戏

思路：

首先我们清楚，交换任意两个相邻大臣的位置，对其他大臣获得的金币数不会造成影响。题目要求使得获得奖赏最多的大臣，所获奖赏尽可能的少，也就是让最大值尽可能小，并且国王固定在队伍的最前面，所以我们考虑后面的大臣即可。

在n(n≥2)个大臣中找出任意相邻的两个大臣A与B，记他们左右手的值分别为 、 、 、 ，以及在A之前的所有大臣和国王左手上数字的乘积为

前乘积	A	B
	、	、

假如此时A和B获得的金币数的最大值最小，则我们有不等式
,   即A、B获得的金币数的最大值小于等于交换位置后B、A获得的金币数的最大值

很显然：


结合上面的不等式，我们可以推断出：

化简得到：

所以，我们只需要对大臣们进行排序，让他们满足上面化简得到的不等式，
排序完了以后再从第一个大臣开始遍历，找到最多需要多少个金币即可

代码

*对于 100%的数据，有 1 ≤ n ≤1,000,0 ＜ a,b ＜ 10000。数据过大，这里无耻的复制了别人的大数计算的代码

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

using namespace std;

typedef struct people {
    int leftHand;   //左手上的数
    int rightHand;  //右手上的数
} people;

//需要用到大数计算

//一个大数乘一个int数
//返回num1 * num2
vector<int> multiply(const vector<int> &num1, int num2) {
    int carry = 0;    //记录进位
    vector<int> ans;    //记录答案
    for (int i = 0; i < num1.size() || carry != 0; ++i) {
        //如果还在num1的范围内，和num1相乘一位
        if (i < num1.size()) {
            carry += num1[i] * num2;
        }
        ans.push_back(carry % 10);
        carry /= 10;
    }
    return ans;
}

//一个大数除一个int
//返回 num1 / num2
vector<int> divide(const vector<int> &num1, int num2) {
    int temp = 0; //工具人变量，用来做除法
    vector<int> ans;    //记录答案
    //倒着循环，因为大数是倒着记的
    for (int i = num1.size() - 1; i >= 0; --i) {
        temp = temp * 10 + num1[i];
        ans.push_back(temp / num2);
        temp %= num2;
    }
    //因为大数是倒着记的，所以输出的答案也要倒过来，顺便把前面多出来的0删掉
    reverse(ans.begin(), ans.end());
    while (ans.back() == 0 && ans.size() > 1) {
        ans.pop_back();
    }
    return ans;
}

//判断num1是否大于num2
bool operator>(const vector<int> &num1, const vector<int> &num2) {
    //如果num1和num2位数不同，位数多的数更大
    if (num1.size() != num2.size()) {
        return num1.size() > num2.size();
    }
    for (int i = num1.size() - 1; i >= 0; --i) {
        if (num1[i] != num2[i]) {
            return num1[i] > num2[i];
        }
    }
    return false;
}

//输出大数
ostream &operator<<(ostream &output, vector<int> &num) {
    for (int i = num.size() - 1; i >= 0; --i) {
        output << num[i];
    }
    return output;
}

int main() {
    int temp;   //工具人变量
    int n;  //总人数（国王+大臣）
    cin >> n;
    n++;
    people pps[n];  //pps[0]为国王，其他为大臣
    for (int i = 0; i < n; ++i) {
        cin >> temp;
        pps[i].leftHand = temp;
        cin >> temp;
        pps[i].rightHand = temp;
    }
    //对大臣进行排序，让最大的金币数最少
    for (int i = 1; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (pps[i].leftHand * pps[i].rightHand > pps[j].leftHand * pps[j].rightHand) {
                swap(pps[i], pps[j]);
            }
        }
    }
    vector<int> coins, maxCoins; //金币数和最大金币数
    coins.push_back(pps[0].leftHand);
    for (int i = 1; i < n; ++i) {
        vector<int> tempCoins = divide(coins, pps[i].rightHand);  //第i个大臣的金币数
        if (tempCoins > maxCoins || maxCoins.empty())maxCoins = tempCoins;
        coins = multiply(coins, pps[i].leftHand);
    }
    cout << maxCoins;
}