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

$\text{[Problem Discription]}$

$\text{[Analysis]}$

首先得注意这么一点：$k$ 必须得是 $n$ 的因数（这里的 $n,k$ 对应于题目的 $N,K$），不然不合法。

其实这虽然是限制，但是这个限制其实是使得题目的难度大大降低了。因为这样每组的宠物数量相同，有完全相同的规律，不需要特殊讨论。

每组 $k$ 只宠物，一共需要分成 $c=\frac{n}{k}$ 组。

对于每组宠物，假设被感染的宠物数量为 $x$。调动我们残存的高中知识，我们惊喜地发现，$x$ 服从二项分布。于是我们知道 $E(x)=kp$。

但是这并没有什么用。我们需要知道的是有宠物感染病毒的概率。正难则反，没有宠物感染病毒的概率是 $p^k$，所以有宠物感染病毒的概率就是 $\left(1-p^k\right)$。

一旦有动物感染，就需要重新进行 $k$ 次测试。于是每一组测试次数的期望值是 $k+k\times \left(1-p^k\right)$。

一共有 $c$ 组，由期望的线性可加性知，总的期望即为 $n\times \left[k+k\times \left(1-p^k\right)\right]$，化简即为 $nk+n\times \left(1-p^k\right)$。

一个快速幂，加上枚举即可。总时间复杂度 $O(n\log n)$。不过这个时间复杂度好像有点问题？反正就是线性对数就对了。

另外：不要忘记特判 $k=1$ 的情况。$k=1$ 时的检测次数就是 $n$！！！

$\text{Code}$

int n,ans;double p,minn;double ksm(double u,int v){快速幂自己写，太简单啦
}double f(int k){return n/k+n*(1-ksm(1-p,k));
}int main(){cin>>n>>p;minn=n;ans=1;//特判 k=1for(int i=2;i<=n;i++)if (n%i==0){double tmp=f(i);if (tmp<minn){minn=tmp;ans=i;}}printf("%d",ans);return 0;
}