题目跳转： [P1080] 国王游戏(简化版)

贪心

据题，在任意顺序的排列下，期望让 得到最多金币的臣子 得到的金币数最小。

解题思路

设当前累乘得到的积为，第i个臣子在左/右手写下的数字分别为 、。

首先我们根据题目得到第i个臣子能够得到的金币数量为：

而对于所有臣子，我们希望能够让 值最小，因此我们需要使得 尽可能小。

因为公式是通用的，所以易得数列 任意相邻两项均满足：

约去相同项得到：

再次整理得到：

由此我们已经清楚的知道了我们的目的——通过改变臣子的顺序，使得数列中任意相邻两项的值的最大值尽可能小，即使得 尽可能小。

代表不改变原有顺序的情况下大臣和大臣中最大的那个值为多少。 则是交换大臣和大臣位置后最大那个值为多少。

因此我们需要不断的比较相邻两项，并选择 和 中相对较小的那种顺序作为恰当的顺序，重新排列大臣的顺序。

我们需要使最大值最小化，故选取的情况。

所以我们实际上是选择 中第二大的元素作为正确的顺序。

由于 , 易知 , ,因此我们只需要比较每个臣子的即可。

所以问题最后就变成了依据对所有臣子进行排序，并计算该情况下的。

我的排序思路是以初始顺序作为编号，并用 编号-臣子书写的数字 和 臣子的左右数字之积-编号 两个vector来查找，直接对臣子的左右数字之积-编号容器进行排序并计算。

时间复杂度应该为 ，输入和计算为 ，排序算法为。

空间复杂度为，数个一位数组储存数字。

我做的时候没出现累乘超出数据范围的情况，没用到高精度，可能是数据范围改过。

如果出现错误，感谢指出。

下附代码：

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

bool cmp(const pair<int, int> &x, const pair<int, int> &y){	//自定义排序
    return x.first < y.first;
}

int main(){
	int n;
    cin >> n;
    long long a, b;
    cin >> a >> b;
    vector<int> l(n, 0);		//编号-大臣数字
    vector<int> r(n, 0);
    vector<pair<int, int>> mp(n);//大臣乘积-编号
    for(int i = 0; i < n; i++){
    	cin >> l[i] >> r[i];
        mp[i] = {l[i]*r[i], i};
    }
    sort(mp.begin(), mp.end(), cmp);	//排序
    long long maxv = 0;
    for(int i = 0; i < n; i++){
        int idx = mp[i].second;
        int curl = l[idx];
        int curr = r[idx];
        if(a/curr > maxv){
            maxv = a/curr;
        }
        a *= curl;
    }
    cout << maxv;
	return 0;
}