【2024.2.4练习】国王游戏

本文主要是介绍【2024.2.4练习】国王游戏，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

题目思路

涉及排列组合求最优解问题，数据大考虑是否满足某种贪心策略。

假设不除以右手的数字，那么获得金币数量最多的显然为最后一个人。左手数字最大的应排在最后一位。在右手有数字的情况下，不妨也尝试从最后一个人开始排。

假设最后一个为第 $n$ 个人（国王为第0个），他左手和右手上的数字分别为 $L_n$ 和 $R_n$ ，他获得的金币为 $G_n$ 。则：

① $G_n= L_0\times \frac{L_1\times L_2\times ...\times L_{n-1}}{R_n}$

假设将他和第一个大臣交换位置，则最后一个获得的金币变成：
② ${G_n}' = L_0\times \frac{L_n\times L_2\times ...\times L_{n-1}}{R_1}$

将①式与②式相除，得：
③ $\frac{G_n}{G_n{}'} =\frac{L_1\times R_1}{L_n\times R_n}$

要使最后一个人获得的金币数尽可能少，应使 $G_n\leq G_n{}'$ ，则 $L_nR_n$ 应尽可能大。

现在我们已经知道了使最后一个获得金币最少的策略。接下来需证明所有人都用这种策略就能使最大金币数最小。假设最后一个人可能获得金币的数量有 $k$ 种，分别为 $A_1,A_2,A_3...A_{k}$ ，分别对应第 $k$ 个人在最后一个位置上时获得金币数。倒数第二个人可能获得金币的数量有 $k-1$ 种，分别为 $B_1,B_2,B_3...B_{k-1}$ ，因为已经有一个人排到了最后一个位置上。

易证： $A_i> B_i$

因此，每次应选取 $A_i$ 中最小的那一个，这样剩余的 $A_i$ 在转化成 $B_i$ 时值都会减小，按此策略选择出的最大金币数也是最小的。

还有一个细节，当两个 $L_nR_n$ 的值相同的时候应先排哪个？
当 $L_iR_i=L_jR_j$ ，设先排 $L_iR_i$ ，则：

$G_i= L_0\times \frac{L_1\times L_2\times ...\times L_{j-1}\times L_{j}}{R_i}$

$G_j= L_0\times \frac{L_1\times L_2\times ...\times L_{j-1}}{R_j}$

两式相除得： $\frac{G_i}{G_j} =\frac{L_j\times R_j}{R_i}=L_i$

可以看出后排获得得金币数 $G_j=G_i/L_i$ ，为了使后一个获得的金币数尽可能少，故两个 $L_nR_n$ 的值相同的时候应先排 $L_n$ 更高的。

我的代码

为了求 $ab$ 的最大值，需要在执行贪心策略的过程中使用排序算法，由于排序中涉及两个变量，故采用map容器排序，时间复杂度为 $O(nlogn)$ 。由于部分数据范围需要高精度算法。高精度部分尚未实现。

#include <iostream>
#include <algorithm>
#include <map>
#include <set>
using namespace std;
typedef multiset<int> s;
typedef pair<int, s> p;
map<int, s> m;
map<int, s>::iterator it;
multiset<int>::iterator it2;
int a[1001];
int b[1001];
int main() {int n;//快速排序cin >> n;cin >> a[0] >> b[0];for (int i = 1; i <= n; i++){s S;cin >> a[i] >> b[i];S.insert(a[i]);//向map容器插入数据pair<map<int, s>::iterator, bool> flag = m.insert(p(a[i] * b[i], S));//检查元素是否冲突(ab相等)if (!flag.second) {s S2((*flag.first).second);S2.insert(a[i]);m.erase(flag.first);m.insert(p(a[i] * b[i], S2));}}//执行贪心long long mult = a[0];long long ans = 0;for (it = m.begin(); it != m.end(); it++) {s S((*it).second);for (it2 = S.begin(); it2 != S.end(); it2++) {long long L = *it2;//cout << L;long long R = (*it).first / L;//cout << R;ans = max(ans, (mult / R));mult = mult * L;}}cout << ans<< endl;return 0;
}

这篇关于【2024.2.4练习】国王游戏的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！