题解：P10786 [NOI2024] 百万富翁

· · 题解

由于交互库是适应性的（至少题目是这样说的），我们要找出 k 个人中存款金额最多的那一个，只能将 k 个人两两询问，需要的询问数为 \frac{k \times (k-1)}{2}，不妨设 f(x)=\frac{x \times (x-1)}{2}。

对于测试点 1，可以发现 499500 = f(1000)，可以对每一组 (i,j) 询问一次，就可以得出这一组最大值的编号。

对于测试点 2：

对于每一次询问，我们可以将存款金额最多的人的候选人人数减少，直到减少到只剩一个人，就可以得出答案。我们可以把每一次询问后剩下的候选人数量表示成一个序列 l。

首先考虑如何进行询问：

设询问前有 a 个候选人，询问后有 b 个候选人。

最佳策略是将 a 个人分成 b 组，每组 \lfloor\frac{a}{b}\rfloor 或 \lfloor\frac{a}{b}\rfloor+1 个人，需要的询问数就是：

g(a,b) = (b-(a \bmod b)) \times f(\lfloor\frac{a}{b}\rfloor)+(a \bmod b) \times f(\lfloor\frac{a}{b}\rfloor+1)

则请求数 t 为序列 l 的长度减 1，所有请求的查询次数总和 s 为 \sum_{i=0}^{t}{g(l_i,l_{i+1})}。

要想拿到满分，就需要找到满足 t \le 8 \text{, } s \le 1099944 的序列 l，这里提供模拟退火算法的 python 实现。

import random

def f(x: int) -> int:
    return (x*(x-1))//2

def g(a: int, b: int) -> int:
    return (b-(a % b))*f(a//b)+(a % b)*f(a//b+1)

def get_val(l: list[int]) -> int:
    l = [1000000]+l+[1]  # 退火时不用考虑总人数 1000000 和剩下的人数 1
    res = 0
    for i in range(len(l)-1):
        res += g(l[i], l[i+1])
    return res

def get_valid(l: list[int]) -> bool:
    return all(i > 0 for i in l)  # 保证不出现 l 中有一项小于等于 0 的情况

def simulate() -> list[int]:
    while True:
        cur_l = [500000, 250000, 125000, 62500, 31250, 15625, 7812]  # 初始序列
        cur_l_val = get_val(cur_l)
        temp = 200000.0  # 初始温度
        dec = 0.999  # 降温速度
        while temp > 1:
            new_l = []
            for i in range(len(cur_l)):
                dis = round(temp/(2**i))  # 序列中越靠后的数字绝对值越小，需要的改动幅度就越小，所以除 2 的 i 次方
                new_l.append(cur_l[i]+random.randint(-dis, dis))
            if not get_valid(new_l):
                continue
            new_l_val = get_val(new_l)
            if new_l_val < cur_l_val:
                cur_l_val = new_l_val
                cur_l = new_l
            temp *= dec
        if cur_l_val <= 1099944:
            return cur_l

print(simulate())

这段代码的平均运行时间小于 10 秒，运行多次后得出了 7 组不同的满足要求的序列：

[1000000, 500000, 250000, 125000, 62496, 20832, 3472, 183, 1]
[1000000, 500000, 250000, 125000, 62497, 20832, 3472, 183, 1]
[1000000, 500000, 250000, 125000, 62498, 20832, 3472, 183, 1]
[1000000, 500000, 250000, 125000, 62499, 20832, 3472, 183, 1]
[1000000, 500000, 250000, 125000, 62499, 20833, 3472, 183, 1]
[1000000, 500000, 250000, 125000, 62500, 20832, 3472, 183, 1]
[1000000, 500000, 250000, 125000, 62500, 20833, 3472, 183, 1]