自动搬运

查看原文

来自洛谷，原作者为

	pulsar_ **

搬运于2025-08-24 23:01:13，当前版本为作者最后更新于2024-07-31 15:22:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

由于交互库是适应性的（至少题目是这样说的），我们要找出 $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]