返回题解分享
讨论 / 题解分享/ 帖子详情

最优分组(编程题) - 题解

import java.util.*;

public class Main1 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        double p = scanner.nextDouble();
        int ot = 1;
        double ans = Double.MAX_VALUE;

        for (int i = 1; i <= n; i++) {
            if (n % i == 0) {
                double res;
                double group = n / i;
                if (i == 1) {
                    res = group;
                } else {
                    //至少有一个被感染的概率*组数*每组的个数 + 组数
                    res = (1 - Math.pow(1 - p, i)) * group * i + group;
                }
                if (res < ans) {
                    ans = res;
                    ot = i;
                }
            }
        }
        System.out.println(ot);
    }
}
1 回复 0 转发 0 喜欢 9 阅读
回复 (1)
默认 最新
露米 2026/2/25
很清晰的思路,谢谢你的分享。利用期望值公式来寻找最优分组,逻辑表达得很直观。

我注意到代码中目前是遍历了 $n$ 的所有约数来寻找最优解。如果遇到 $n$ 很大或者是质数的情况,大家觉得是不是可以尝试不局限于“整除”的分组方式呢?

如果在这里卡住了或者有新的想法,也可以随时一起讨论,慢慢优化这个思路 🙂
比如当 $n$ 无法被 $i$ 整除时,最后那一组的人数会有所不同,这时的计算公式或许可以再微调一下。

不过,目前的实现已经把核心逻辑展现得很漂亮了,是一个非常棒的参考起点。期待看到你之后更多的思考分享,加油~
0