P11045 [蓝桥杯 2024 省 Java B] 最优分组

Link: https://www.luogu.com.cn/problem/P11045

题目描述

小蓝开了一家宠物店，最近有一种 X 病毒在动物之间进行传染，小蓝为了以防万一打算购买测试剂对自己的宠物进行病毒感染测试。

为了减少使用的测试剂数目，小蓝想到了一个好方法：将 $N$ 个宠物平均分为若干组，使得每组恰好有 $K$ 只宠物，这样对同一组的宠物进行采样并混合后用一个试剂进行检测，如果测试结果为阴性则说明组内宠物都未感染 X 病毒；如果是阳性的话则需要对组内所有 $K$ 只宠物单独检测，需要再消耗 $K$ 支测试剂（当 $K=1$ 时，就没必要再次进行单独检测了，因为组内只有一只宠物，一次检测便能确认答案）。

现在我们已知小蓝的宠物被感染的概率为 $p$，请问 $K$ 应该取值为多少，才能使得期望的测试剂的消耗数目最少？如果有多个答案，请输出最小的 $K$。

输入格式

第一行，一个整数 $N$。

第二行，一个浮点数 $p$。

输出格式

输出一行，一个整数 $K$ 表示答案。

输入输出样例 #1

输入 #1

1000
0.05

输出 #1

5

说明/提示

【评测用例规模与约定】

对于 $30\%$ 的评测用例：$1\le N\le 10$。

对于 $60\%$ 的评测用例：$1\le N\le 1000$。

对于 $100\%$ 的评测用例：$1\le N\le 10^6$，$0\le p\le 1$。

---

Solution

1. 问题简述

对传染病进行试剂检测时，多人混合检测的数学模型（这种检测方法也出现在 COVID-19 的疫情中）。

2. 分析

设总共有 $N$ 个个体，分成了 $g=N/K$ 组，每一组有 $K$ 个个体，设总共消耗了 $X$ 份检测试剂。

容易看出 $g=1$ 或 $g=N$ 时相当于不分组，$E(X)=N$。

从 $g\ge 2$ 开始，首先需要消耗 $g$ 支试剂为每一组进行一次检测。在每一组当中：

• 只要有 $1$ 个个体为阳性，整组就会显阳性；
• 至少一个阳性的对立事件是所有个体全为阴性；
• 由于每个个体的阳性与否相互独立，阳性的概率全为 $p$，所有个体全部为阴性的概率就是 $(1-p{)}^K$，因此某一组显阳性的概率就是 $1-(1-p{)}^K$。

设在此期间有 $Y$ 组检测结果为阳性，则容易知道 $Y\sim B(g,1-(1-p{)}^K)$，服从二项分布，根据二项分布的数学期望公式可知
$$E(Y)=g[1-(1-p{)}^K]=\frac{N}{K}[1-(1-p{)}^K]$$

对于每一个阳性的组都需要额外消耗 $K$ 支试剂分别检测一次，因此 $g\ge 2$ 时总体消耗的试剂数量的数学期望
$$E(X)=KE(Y)+g=\frac{N}{K}+N[1-(1-p{)}^K]$$

由于 $N$ 不超过 $10^6$，因此直接一遍遍在保证 $N$ 能够整除 $K$ 的情况下尝试最优解即可。

3. 代码

using System;

class P11045
{
	public static void Main()
	{
		double n, p;
		n = Convert.ToDouble(Console.ReadLine());
		p = Convert.ToDouble(Console.ReadLine());
        double mean = n;
        int optimal_group = 1;

        for (int k = 2; k <= n; k++)
        {
            if (n % k == 0)
            {
                double current = n / k + n * (1 - Math.Pow(1 - p, k));
                if (mean > current)
                {
                    optimal_group = k;
                    mean = current;
                }
            }
        }
        Console.WriteLine(optimal_group);
    }
}

4. Extra

作为对这道题的拓展，个人觉得这部分内容虽然本题不涉及（因为已经限定了分组时必须每组相同，如果总数为质数就不能分组）但是还是有必要提一下。本题提到的“多人混检”出现在 2021 年的北京高考数学卷中（下图），也出现在一些其他的数学比赛中，因此这个模型的典型性可见一斑。

在这里我们丢弃掉整除的限定条件，将上述表达式里面的 $E(X)$ 除以 $N$，可以得到检测过程中平均每个人需要消耗的试剂数

$$E_p=1+\frac{1}{K}-(1-p{)}^K$$

由于这个表达式的值和总人数 $N$ 无关，因此具有更强的普适性（也就是说单纯从数学理论上讲，题目里输入的人数 $N$ 其实没用）。我们设函数

$$f(x)=1+1/x-(1-p{)}^x$$

绘制函数代码和图像如下：

import matplotlib.pyplot as plt
import numpy as np

plt.rcParams["font.family"] = "SimHei"

p = [0.001, 0.010, 0.050, 0.200]
x = np.linspace(1, 40, 1000)

for i in range(len(p)):
    y = 1 + 1 / x - (1 - p[i]) ** x
    plt.plot(x, y, marker = None, label = "p=%.3f"%p[i])

plt.legend()
plt.xlabel("分组组数")
plt.ylabel("人均消耗试剂")
plt.title("试剂消耗和组数的关系")

plt.show()

从上面的图线可以看出

1. 感染率越高，最优的分组人数就越少。例如感染率为 $0.01$ 时，人均消耗的试剂在每一组为 $10$ 人时达到最低，感染率为 $0.20$ 时，这个最小值的人数为 $4$；
2. 感染率越高，这个最小值也会越大。

由于用最朴素的方法，每个人都需要消耗 $1$ 支试剂，因此我们看看什么时候能够让 $f(x)<1$。

$$1+1/x-(1-p{)}^x<1\Rightarrow p<1-\frac{1}{x^{1/x}}$$

因此当感染率 $p$ 和混检人数 $x$ 满足上面的不等式关系时，混合检测就会优于传统的方法。

我们来看一看阈值（threshold）函数 $t(x)=1-1/x^{1/x}$ 的变化情况。

求解函数最小值/最大值的通用方法是求导。对于 $t(x)$ 而言，有

$$t^{\prime }(x)=\frac{1}{x^{1/x}}\cdot \frac{\ln x-1}{x^2}$$

因此当 $x=e$ 时，$t^{\prime }(x)=0$，$t(x)$ 达到峰值为 $1-\frac{1}{e^{1/e}}$，约为 $0.308$。也就是说如果某种传染病的感染率超过了 $30.8\%$，混检就会变得毫无意义，因为不论分为多少组都会导致每人平均消耗超过 $1$ 份试剂。

现在回到之前的 $f(x)$，对 $x$ 求导得到：

$$f^{\prime }(x)=-1/x^2-(1-p{)}^x\cdot \ln (1-p)$$

考虑到上述的 $f^{\prime }(x)$ 中的 $x$ 出现在分母也出现在指数，因此是超越函数，一般无法求出其精确解，但是可以通过一些数学方法求出近似数值解。

例如，当 $p=0.05$ 时，可以求出 $f^{\prime }(x)=0$ 的三个数值近似解

$$x_1=-3.9863,x_2=5.0224,x_3=132.6825$$

很明显 $x_1$ 是没用的，而上述的 $x_2$ 恰好就对应了输出样例的 $5$。如果检测方面有钱且任性，非要选择一种消耗试剂最多的方案，那么这个值就出现在 $132\sim 133$ 左右。