java - 异加数问题贪心算法

Question

我尝试用贪心算法解决不同加数问题

问题描述

任务。这个问题的目标是将给定的正整数 𝑛 表示为尽可能多的成对的总和尽可能不同的正整数。即求最大值𝑘这样 𝑛可以写成 𝑎1 + 𝑎2 + · · · + 𝑎𝑘其中 𝑎1, . . . , 𝑎𝑘是正整数并且𝑎𝑖 ̸= 𝑎𝑗对于所有 1 ≤ 𝑖 < 𝑗 ≤ 𝑘.

输入格式。输入由单个整数 𝑛 组成。约束。 1 ≤ 𝑛 ≤ 10^9 .

输出格式。 第一行输出最大数𝑘这样 𝑛可以表示为总和的 𝑘成对不同的正整数。第二行输出𝑘成对不同的正整数总计为 𝑛 (如果有很多这样的表示，输出其中的任何一个)。

我的代码:

public class DifferentSummands {
    private static List<Integer> optimalSummands(int n) {
        List<Integer> summands = new ArrayList<Integer>();
        int start = 1;
        int newNumber = n;

        if (n == 2) {
            summands.add(2);
            return summands;
        }

        while (true) {
            if (summands.contains(newNumber - start)) {
                start++;
                continue;
            } else {
                newNumber -= start;
                summands.add(start);
                start++;
            }

            if (newNumber == 0) {
                return summands;
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        List<Integer> summands = optimalSummands(n);
        System.out.println(summands.size());

        for (Integer summand : summands) {
            System.out.print(summand + " ");
        }
    }
}

如果输入太大需要大约 3.24 秒，而最大可用时间为 1.5 秒，我的代码就会失败。

Answer 1

用至少 k 个不同的加数可以得到的最小数字就是从 1 到 k 所有数字的总和。 任何小于该数字的加数都将更少...最多k-1。

高斯有一个计算从 1 到 k 的数字总和的公式。它只是 k(k+1)/2。

您只需要找到最大的 k 使得 k(k+1)/2 <= n。从上面，你知道如果 k 再大一点，你就不能把 n 分成那么多的加数，所以这是最大可能的答案。

实际生成 k 加到 n 上的加法也很容易——它只是从 1 到 < strong>k-1，然后剩下的(n - k(k-1)/2)。

您可以直接求解k:

k(k+1)/2 <= n

k² + k - 2n <=0

k <= (sqrt(8n+1)-1)/2

最后一步是通过二次公式。因为你想要最大可能的 k，它只是

k = floor((sqrt(8n+1)-1)/2)