通过迭代数组并将每个元素除以一个以1开头的数字,找到一个最小值

如果没有具体的理由做数学题。对于每个比率,而不是最终的和,你可以先得到所有元素的和,然后找到c的值

总额/c<=要点

总和/积分<=C

如果0<(总和/点数)<1,c=1

否则c=数学。ceil(总和/分)

public static int findMin(List<Integer> distance, int points) {
    AtomicInteger c = new AtomicInteger(1);
    while (distance.stream().mapToInt(d -> d / c.get()).sum() > points) c.incrementAndGet();
    return c.get();
}

如果我错了,请纠正我,但假设距离集为 [1, 2, 3] 正当然后你从 1/1 + 2/1 + 3/1 这(让我们把它们留作分数)等于 6/1 ,因为它们在这里都有相同的“分母”,所以它不会改变。这意味着第一次迭代,除以1,实际上就是这些值的总和。 (1 + 2 + 3) / 1 除以一。任何除以1的东西都是它自己。所以这只是总数。

现在第二遍,如果我假设正确, 1/2 + 2/2 + 3/2 --再次把它们作为分数-- (1 + 2 + 3) / 2 = 6/2 .现在你应该看到一种模式了,对吧?第一关是 6/1 二是 6/2 接下来是 6/3 ...

那么:

public static int findMin(List<Integer> distance, int points) {
    int sum = 0;
    for (Integer i : distance) {
        sum += i;
    }

    int min = 1;
    while (sum / min > points) {
        min += 1;
    }

    return min;
}

也许这样的解决方案会奏效?

编辑 结果证明,这个解决方案假设(至少部分地)有一定的数学精度,然而,似乎每个元素的除法必须是整数除法,如果我们严格地从数学上接近它,这会使一些结果产生偏差。因此,虽然不是问题的直接答案,但我觉得离开这里作为解决方案是正确的。

我认为我们可以做两件事来提高性能,但这种方法不是最好的,它取决于你的列表数量:

• 减少迭代次数
• 使用贪心算法降低优先级的最大值。为了做到这一点,我们首先需要对列表进行排序,它可能需要花费O(nlog(n))时间。

代码是这样的

public static int findMin(List<Integer> distance, int points) {
    int sum = 0;
    int c = 1;
    // sort the list for implement greedy algorithm
    Collections.sort(distance, Comparator.reverseOrder());
    while (true) {
        for (Integer dist : distance) {
            sum += dist / c;
            // reduce the times of iterate
            if (sum <= points) {
                return c;
            }
        }
        c++;
        sum = 0;
    }
}