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

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

视频中标准程序代码如下:

import java.util.Scanner;

public class Main {
    static final int N = (int) 1e6 + 10;
    static double[] f = new double[N];
    static double[] g = new double[N];

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        double p = scanner.nextDouble();
        double ans = Double.MAX_VALUE;
        int ot = 1;
        double np = 1 - p;
        for (int i = 1; i <= n; i++) {
            f[i] = 1 - np;
            g[i] = np;
            np *= (1 - p);
        }
        double m = 1.0 * n * p;
        for (int i = 1; i <= n; i++) {
            if (n % i == 0) {
                double group = n / i;
                double res;
                if (i == 1) {
                    res = group;
                } else {
                    res = group * (f[i] * (i + 1) + g[i]);
                }
                if (res < ans) {
                    ans = res;
                    ot = i;
                }
            }
        }
        System.out.println(ot);
    }
}
2 回复 0 转发 0 喜欢 12 阅读
回复 (2)
默认 最新
露米 4 天前
谢谢你分享这段代码,逻辑写得很整洁。

通过预处理数组来存储概率,确实能让主循环里的期望计算变得很直观。我注意到目前的实现里,最优解 ot 是在 $n$ 的约数中寻找的,这在特定条件下是一个很高效的剪枝思路。

如果大家在练习时,遇到了 $n$ 很大且约数较少的情况,或者 $n$ 无法被完美分组时,也可以试着讨论一下该如何调整计算逻辑。

在这个过程中如果遇到卡壳的地方,
可以随时在这里分享你的想法,我们可以一起拆解问题。

慢慢来就好,这种思考的过程本身就很有价值 🙂
0
露米 2026/2/6
谢谢你分享这段代码。逻辑整理得很清晰,尤其是通过预处理概率来计算期望值的部分,读起来很顺畅。

这个题目背后的概率模型其实挺有意思的。如果 $p$ 的取值发生变化,最优的 $i$ 也会随之移动。大家在练习的时候,也可以试着观察一下当 $p$ 非常小或者非常大时,分组方案会倾向于什么样的变化。

另外我也在想,目前的实现是考虑了 $n$ 能被 $i$ 整除的情况。如果 $n$ 比较大且不一定是 $i$ 的倍数,最后余下的那一组该如何处理,会不会对最优解产生影响呢?如果大家有新的发现,也欢迎一起讨论 🙂
其实在处理这类问题时,考虑非整除的情况往往是通往更普适解法的关键一步。

期待看到大家更多的思考,我们一起在交流中进步 🌿
0