Головоломка с алгоритмом: минимальная стоимость, позволяющая всем людям, стоящим в очереди, общаться друг с другом

Мы можем сделать следующее в O(n):

Рассчитайте стоимость перемещения всех людей справа от человека i по направлению к человеку i на приемлемое расстояние:

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

Не совсем уверен, как сформулировать это эффективно.

Вот жадный алгоритм, написанный на Java, но я не знаю, дает ли он оптимальное решение в каждом случае. Также это скорее доказательство концепции, есть место для оптимизации.

Он основан на том факте, что два соседних человека не должны находиться друг от друга более чем на К, следующий сосед не должен быть дальше, чем на 2К, и так далее. На каждом этапе мы перемещаем человека, который «больше всего нарушает эти ограничения». Детали этого расчета находятся в методе 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;
    }
}