28776: 国王游戏

greedy, http://cs101.openjudge.cn/practice/28776

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

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

输入

第一行包含一个整数 n，表示大臣的人数。

第二行包含两个整数 a 和 b，之间用一个空格隔开，分别表示国王左手和右手上的整数。

接下来 n 行，每行包含两个整数 a 和 b，之间用一个空格隔开，分别表示每个大臣左手和右手上的整数。

1 <= n <= 100, 1 <= a,b <= 10。

输出

一个整数，表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。提示：使用C或C++的同学需要实现高精度乘法，否则数据会溢出。

样例输入

sample1 input:
3 
1 1 
2 3 
7 4 
4 6

sample1 output:
2

# 
按 1、2、3 这样排列队伍，获得奖赏最多的大臣所获得金币数为 2；
按 1、3、2 这样排列队伍，获得奖赏最多的大臣所获得金币数为 2；
按 2、1、3 这样排列队伍，获得奖赏最多的大臣所获得金币数为 2；
按 2、3、1这样排列队伍，获得奖赏最多的大臣所获得金币数为 9；
按 3、1、2这样排列队伍，获得奖赏最多的大臣所获得金币数为 2；
按 3、2、1 这样排列队伍，获得奖赏最多的大臣所获得金币数为 9。
因此，奖赏最多的大臣最少获得 2 个金币，答案输出 2。

样例输出

sample2 input:
18
10 2
5 2
8 8
8 7
4 2
8 1
7 7
10 1
8 5
4 10
2 6
1 1
1 9
1 7
4 7
1 9
4 8
8 9
4 6

sample2 output:
3262236444

提示

greedy

来源

2024 TA-Wjl, https://www.luogu.com.cn/problem/P1080

考虑最后一个大臣，其获得的钱数是所有人左手上的数的乘积（一个定值），除以自己左手和右手的乘积，所以要让他左手右手的乘积最大，所以就有了排序的key。不过这题很奇怪，用floor来取整会wa，用整除就可以。

大臣获得的金币是自己以及前面所有左手乘积除以自己的左右手乘积，从这个思路出发按左右手乘积升序排列即可获得最大值的最小值~~，且该值在最后一个大臣处取到~~。不是最后一个是maxmin，反例：国王1 1，三个大臣，6 1;4 2;1 10。

这个greedy思路感觉最好理解。这种情况下左右手成绩最大的一定在最后，才能让获得的金币尽可能小。

考虑所有人左手的总乘积 $Π$ 一定，最后一个人的奖赏就是 $Π$ /(a*b)，所以只要按左右手乘积排序就行。不难证明，这样的排序下任何换位的行为都会增大最大值。

对于任何一个人，他都是在最后一个时获利最大，而对于任何一种情况下的最后一人，他的获利都是左手们的总乘积除以自己的左右手乘积。

python

"""
直接想很难想到贪心策略，不妨逆推一下，我们先假设有了一个排列，然后看怎么换排列中大臣的顺序能得到更优的结果

首先，交换第i个大臣和第j个大臣(i<j)，不会影响1~i-1中的大臣的结果和第j+1~n中的大臣的结果
设1到i-1所有大臣的左手的乘积为x_1(包括国王)，i+1到j-1中所有大臣的左手乘积为x_2，第i个大臣右手的数为r_i,左手为l_i，第j个大臣右手的数为r_j左手为l_j。
不交换i和j:
第i个大臣获得金币:w_1[i] = x_1 / r_i
第j个大臣获得金币:w_1[j] = x_1 * x_2 * l_i / r_j
ans = max(ans, w_1[i], w_1[j])
交换i和j:
第i个大臣获得金币:w_2[i] = x_1 * x_2 * l_j / r_i
第j个大臣获得金币:w_2[j] = x_1 / r_j
ans = max(ans, w2[i], w2[j])
显然w_2[i]>w_1[i], w_1[j]>w_2[j]
ans = max(ans, w_2[i],w_1[j])

若w_1[j]>w_2[i](即此时要交换i和j,才能得到ans最优情况,取w_2[i]而不是w1[j]):
化简可得l_i * r_i > l_j * r_j
也就是说，当一个大臣左右手乘积>后面的大臣的左右手乘积时,交换这两个大臣，可以得到最大答案的最小值。
"""
from typing import List
def Solution(n:int, a:int, b:int, lst:List[List]) -> int:
    lst.sort(key=lambda x: (x[0] * x[1]))
    ans = 0
    for i in range(n):
        ans = max(ans, a // lst[i][1])
        a *= lst[i][0]
    return ans
if __name__ == "__main__":
    n = int(input())
    a, b = map(int, input().split())
    lst = []
    for i in range(n):
        lst.append([int(_) for _ in input().split()])
    # 时间复杂度O(nlogn)，空间复杂度O(n)

    print(Solution(n, a, b, lst))

黄鹤鸣、光华管理学院

分析: 考虑两个大臣 $p_{1}, p_{2}$ ，它们站在国王 $p_{0}$ 的身后，则这两个大臣有两种排列方案：

1.初始

person	left	right
$p_{0}$	$a_{0}$	$b_{0}$
$p_{1}$	$a_{1}$	$b_{1}$
$p_{2}$	$a_{2}$	$b_{2}$

2.调整

person	left	right
$p_{0}$	$a_{0}$	$b_{0}$
$p_{2}$	$a_{2}$	$b_{2}$
$p_{1}$	$a_{1}$	$b_{1}$

对于第一种情况，答案 $ ans_1 = \max\left(\frac{a_0}{b_1}, \frac{a_0 a_1}{b_2}\right) $

对于第二种情况，答案 $ ans_2 = \max\left(\frac{a_0}{b_2}, \frac{a_0 a_2}{b_1}\right) $

显然， $ \frac{a_0 a_1}{b_2} > \frac{a_0}{b_2} $， $ \frac{a_0 a_2}{b_1} > \frac{a_0}{b_1} $

倘若第一种情况更优， $ ans_1 < ans_2 $， $\because \frac{a_0 a_2}{b_1} > \frac{a_0}{b_1} $， $\therefore \frac{a_0 a_2}{b_1} $ 必须 $> \frac{a_0 a_1}{b_2} $

通过上图可以证明，通过按照a*b的升序排列，每次调整可以使得两个数字中的最大值降低，使得最后序列中的最大值达到最低，后遍历每个元素result=max(result,a0//numbers[i][1])得到这个存在的最大值。此处要注意不能使用math.floor！！！math.floor() 将操作数转为浮点数后，可能导致精度问题，尤其当输入是大整数时。你可能期待 result 是整数类型，但使用 math.floor() 会将结果变为浮点数，导致后续的逻辑出错。

python

n=int(input())
a0,b0=map(int,input().split())
numbers=[]
for _ in range(n):
    a,b=map(int,input().split())
    numbers.append((a,b))
numbers.sort(key=lambda x:(x[0]*x[1]))
result=0
for i in range(n):
    result=max(result,a0//numbers[i][1])
    a0*=numbers[i][0]
print(result)

黄泓博、24工学院，国王游戏就是一个冒泡排序

python

def multiply(index):
    # 初始化乘积m为kl
    m = kl
    # 计算从q数组中前index个元素的第一个值的乘积
    for x in range(index):
        m *= q[x][0]
    return m

# 读取输入n，表示后续会有n对整数输入
n = int(input())
# 读取两个整数kl, kr
kl, kr = map(int, input().split())
# 初始化列表q用于存储每对整数，res用于保存最终结果
q, res = [], 0

# 读取n对整数并存入q列表
for _ in range(n):
    l, r = map(int, input().split())
    q.append([l, r])

# 对q进行排序，先按第一个元素升序排序，再按第二个元素升序排序
q.sort(key=lambda x: x[0])
q.sort(key=lambda x: x[1])

# 对q中的元素进行某种形式的调整（这部分逻辑看起来比较复杂，可能需要进一步检查其正确性）
for i in range(1, n):
    curl, curr = q[i]
    for j in range(i-1, -1, -1):
        jl, jr = q[j]
        if max(multiply(j+1)//curr, multiply(j)//jr) > max(multiply(j)//curr, ((multiply(j+1)//jl)*curl)//jr):
            q[j+1], q[j] = q[j], q[j+1]
        else:
            break

# 遍历q计算最大结果
for i in range(n):
    res = max(res, multiply(i)//q[i][1])

# 输出结果
print(res)

28776: 国王游戏 ​

28776: 国王游戏