2025年洛谷P1080 国王游戏（贪心）

科技前沿 • 2025-01-06 11:13 • 阅读 48

大家好，我是讯享网，很高兴认识大家。

国王游戏

题目描述

恰逢 $H$ 国国庆，国王邀请 $n$ 位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这 $n$ 位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。

国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。

我们先考虑两个相邻的位置 $x$ ， $y$ 情况，我们假设此时位置 $x$ 位置前的所有人的左手连乘为 $p$ 。若另 $x$ 在前，那么此时 $x$ 与 $y$ 的权值分别为 $\frac{p}{b_x}$ , $\frac{p×a_x}{b_y}$ ，若另 $y$ 在前，则权值分别有 $\frac{p}{b_y}$ , $\frac{p×a_y}{b_x}$ 。

那么此时我们假设我们需要另第一种的摆放方式的最大值更小，则有：
$max(\frac{p}{b_x} , \frac{p×a_x}{b_y}) < max(\frac{p}{b_y} , \frac{p×a_y}{b_x})$
因为这里本来就有 $\frac{p×a_x}{b_y} >\frac{p}{b_y}$ ，所以 $max(\frac{p}{b_y} , \frac{p×a_y}{b_x})=\frac{p×a_y}{b_x}$ ，所以就有：
$max(\frac{p}{b_x} , \frac{p×a_x}{b_y}) < \frac{p×a_y}{b_x}$

这里又本来就有 $\frac{p}{b_x}<\frac{p×a_y}{b_x}$ ，所有只要满足下列式子就满足条件：
$\frac{p×a_x}{b_y} < \frac{p×a_y}{b_x}$

即： $a_x×b_x<a_y×b_y$

所以可以得出，若要让 $x$ 摆在前面最大值更小，就必须满足 $a_x×b_x<a_y×b_y$ ，同理我们也可以得到，若要让 $y$ 摆在前面最大值更小，就必须满足 $a_y×b_y<a_x×b_x$ ，那我们也就可以推出，对于仅仅考虑单独的两个位置而言，要让最大值最小，就要另 $a_i×b_i$ 更小的放前面，所以将 $a_i×b_i$ 更小的放前面就会使得答案变得更优，且不会影响前面和后面的权值。所以对于整个序列而言，我们只要发现相邻 $a_i×b_i$ 呈逆序的情况，我们就将其交换，这样可以使得两点间的最大值变得更小，且不影响全局的情况。那么我们不断这样操作，我们就可以将可以变小的地方全部变小了，且我们发现再进行任何操作都只会使答案变得更劣。那么最终操作的结果也就是全局不出现相邻 $a_i×b_i$ 呈逆序的情况，也就是按照 $a_i×b_i$ 排好了。所以我们就按 $a_i×b_i$ 为关键字排好序，直接模拟计算即可。因为数据太大可能会爆，所以得用大数处理。

n = int(input()) t = input().split(' ') A, B = int(t[0]), int(t[1]) a = [] for i in range(0, n): t = input().split(' ') a.append((int(t[0]), int(t[1]))) a.sort(key = lambda x : x[0] * x[1]) mx = 0 for i in range(0, n): if A // a[i][1] > mx: mx = A // a[i][1] A *= a[i][0] print(mx)

讯享网

2025年洛谷P1080 国王游戏（贪心）

国王游戏

题目描述

相关推荐