java - 我的 Google Code Jam Round 1B 2013 "Osmos"代码有什么问题？

Question

我已经通过了样本输入，还有一些我决定提出的输入(即使是极端情况)，但我不知道为什么我得到“不正确”。另外，忽略 quickSort() 调用，我已经实现了它并且工作正常。如果您需要一个概述，这里是问题的链接:https://code.google.com/codejam/contest/2434486/dashboard#s=p0&a=0我什至检查了社论，但我不知道我错过了什么。

Scanner in = new Scanner(System.in);
    int t = in.nextInt();
    for (int i = 0; i < t; i++) {
        int size = in.nextInt();
        int n = in.nextInt();
        int ops = 0;
        int[] sizes = new int[n];
        for (int j = 0; j < n; j++) {
            sizes[j] = in.nextInt();
        }
        quickSort(sizes);
        for (int j = 0; j < n; j++) {
            if (sizes[j] < size) {
                size += sizes[j];
            } else {
                int newSize = (size * 2) - 1;
                if (sizes[j] < newSize) {
                    size = newSize;
                }
                ops++;
            }
        }
        System.out.println("Case #" + (i + 1) + ": " + ops);
    }

Answer 1

那么让我们分析一下您要解决的问题的逻辑。

你有两个选择:

• 删除一个节点
• 添加微尘

目前您只添加微尘，由 newSize = (size * 2) - 1 表示。每次都有效地(几乎)使微尘的大小增加一倍。

如果微尘的新大小仍然不足以捕获循环中当前 j 迭代所表示的微尘怎么办？您需要再次做出选择，是添加另一个微粒，还是移除那个微粒。

假设您的微尘大小为 2，而其他微尘的大小为 1, 1, 3, 5, 8, 1000, 1001。您可以继续添加大量微尘，直到您的微尘可以吸收 1000 和 1001，或者您可以只删除大得离谱的两个微尘。

有了这个启示，迭代似乎并不总能得出最佳答案。在每一步中，您做出的每个选择都是另一条可能的路径，可能可以找到答案，但您希望找到导致最少操作量的决策路径。就好像您想遵循所有可能的路径，然后从找到的最佳解决方案中进行选择。

幸运的是，网上有大量关于此的资源。我建议使用谷歌搜索 pathfinding 和 pathfinding algorithms。这个主题有一些需要学习的地方，但都很有趣。

祝你好运!