算法难题：允许所有站在同一条线上的人相互交流的最小成本

Question

我有一个无法解决的算法设计难题。

谜题的公式是这样的：有N个人站在一条数字线上，每个人都可能站在该线上的任何整数上。多个人可以站在同一个号码上。对于任何两个人能够相互交流，他们之间的距离应小于K。目标是移动他们，使两个人中的每一对能够相互交流（可能通过其他人）。换句话说，我们需要移动它们，使相邻两个人之间的距离小于K。

问题：总移动次数的最小值是多少？这感觉就像是贪婪算法家族或动态规划。任何提示都将不胜感激！

Answer 1

这是一个用Java编写的贪婪算法，但我不知道它是否在所有情况下都给出了最优解。此外，它更像是一个概念证明，还有一些优化的空间。

这是基于这样一个事实，即两个相邻的人之间的距离不得超过K，下一个相邻的人之间的距离不得超过2K，以此类推。在每一步中，我们都会移动“最违反这些约束”的人。有关此计算的详细信息，请参见方法calcForce。

package so;

import java.util.Arrays;

public class Main {

    public static void main(String args[]) {
        int[] position = new int[] {0, 0, 5, 11, 17, 23};
        int k = 5;

        solve(position, k);
    }

    private static void solve(int[] position, int k) {
        if (!sorted(position)) {
            throw new IllegalArgumentException("positions must be sorted");
        }
        int[] force = new int[position.length];
        int steps = 0;
        while (calcForce(position, k, force)) {
            int mp = -1;
            int mv = -1;
            for (int i = 0; i < force.length; i++) {
                if (mv < Math.abs(force[i])) {
                    mv = Math.abs(force[i]);
                    mp = i;
                }
            }
            System.out.printf("move %d to the %s%n", mp, force[mp] > 0 ? "right" : "left");
            if (force[mp] > 0) {
                position[mp]++;
            } else {
                position[mp]--;
            }
            steps++;
        }
        System.out.printf("total: %d steps%n", steps);
    }

    private static boolean calcForce(int[] position, int k, int[] force) {
        boolean commProblem = false;
        Arrays.fill(force, 0);
        for (int i = 0; i < position.length - 1; i++) {
            for (int j = i + 1; j < position.length; j++) {
                int f = position[j] - position[i] - (j - i) * k;
                if (f > 0) {
                    force[i] += f;
                    force[j] -= f;
                    commProblem = true;
                }
            }
        }
        return commProblem;
    }

    private static boolean sorted(int[] position) {
        for (int i = 0; i < position.length - 1; i++) {
            if (position[i] > position[i+1]) {
                return false;
            }
        }
        return true;
    }
}

Answer 2

我们可以在O（n）中执行以下操作：

计算以可接受的距离将所有人移动到peoplei的右侧朝向peoplei的成本：

costRight(A[i]) = costRight(A[i+1]) + (A[i+1] - A[i] - k + 1) * count of people to the right

K = 3;  A = { 0,  3, 11, 17, 21}
costRight = {32, 28, 10,  2,  0}

计算以可接受的距离将人i左侧的所有人移动到人i的成本：

costLeft(A[i]) = costLeft(A[i-1]) + (A[i] - A[i-1] - k + 1) * count of people to the left

K = 3;  A = { 0,  3, 11, 17, 21}
costLeft  = { 0,  1, 13, 25, 33}
costRight = {32, 28, 10,  2,  0}

既然我们有了来自两个方向的成本，我们可以在O（n）中这样做：

minCost = min(costRight + costLeft) for all A[i]
minCost = min(32 + 0, 28 + 1, 13 + 10, 25 + 2, 33 + 0) = 23

但有时这还不够：

K = 3;  A = { 0,  0,  1,  8,  8}

      carry:     -2  -4       3
costLeft  = { 0,  0,  0, 11, 11}

      carry: -3   5      -2
costRight = { 8,  8,  8,  0,  0}

最佳值既不是11也不是8。通过实现最大的节约来测试当前的最佳状态：

move 1 to 2, cost = 1

K = 3;  A = { 0,  0,  2,  8,  8}

      carry:     -2  -2     -10
costLeft  = { 0,  0,  0, 10, 10}

      carry: -2          -2
costRight = { 6,  6,  6,  0,  0}

minCost = 1 + min(0 + 6, 0 + 6, 0 + 6, 10 + 0, 10 + 0) = 1 + 6 = 7

不太确定如何有效地公式化。