二维坐标系旗帜重排最小移动步数问题求解及JS实现需求

问题描述 #

在x-y平面上放置了N个不同的旗帜，需对其进行重排以满足以下条件：

• 所有旗帜的y坐标相同
• 任意两点间的最大距离为N-1
• 所有旗帜处于不同位置

重排时，可将旗帜从(x,y)移动到相邻的上下左右四个方向，每次移动花费1单位代价。要求找出满足条件所需的最小总移动次数，且移动过程中任何时刻不能有两个旗帜处于同一位置。

输入输出要求 #

输入 #

• 第一行输入整数N
• 接下来N行每行输入两个整数xi、yi，表示第i个旗帜的坐标

约束 #

• 1 ≤ N ≤ 100000
• -1000000000 ≤ xi, yi ≤ 1000000000

输出 #

返回一个整数，表示满足条件的最小操作次数

示例 #

示例1 #

2
1 0
2 1

输出： 1
解释： 将旗帜1从(1,0)移动到(1,1)，此时两个旗帜y坐标均为1，x坐标为1和2，最大距离为1=N-1，满足所有条件。

示例2 #

3
1 1
2 2
3 3

输出： 2
解释： 将旗帜1移到(1,2)，旗帜3移到(3,2)，三个旗帜y坐标均为2，x坐标为1、2、3，最大距离为2=N-1，满足条件。

解法思路 #

要满足所有条件，最终的旗帜排列必然是：所有旗帜位于同一水平线（y坐标相同），且x坐标为连续的整数序列（如a, a+1, ..., a+N-1）——这样任意两点的最大距离为(a+N-1)-a = N-1，同时所有位置不同。

最小移动次数可拆解为x方向和y方向的最小代价之和：

1. y方向代价：要让所有旗帜移动到同一y坐标，最小代价的目标y是原所有y坐标的中位数。因为将所有点移动到中位数的总距离（绝对值之和）是最小的。
2. x方向代价：将原x坐标排序后，目标x序列应为连续整数。假设排序后的原x为x_0, x_1, ..., x_{N-1}，对应的目标x应为b, b+1, ..., b+N-1（b为某个整数）。此时每个点的x移动代价为|x_i - (b + i)| = |(x_i - i) - b|，要最小化这个总和，b应取数组[x_0-0, x_1-1, ..., x_{N-1}-(N-1)]的中位数，同样基于绝对值之和最小的性质。

移动过程中避免位置重叠的问题无需额外计算，因为存在合法的移动路径（例如先逐个调整y坐标并保持x不重复，再调整x坐标），且总移动次数的最小值就是x和y方向代价的总和。

JavaScript实现 #

const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

function calculateMinCost(arr) {
    arr.sort((a, b) => a - b);
    const mid = arr[Math.floor(arr.length / 2)];
    let cost = 0n; // 使用BigInt避免大数溢出
    for (const num of arr) {
        cost += BigInt(Math.abs(num - mid));
    }
    return cost;
}

let n;
const xs = [];
const ys = [];

rl.on('line', (line) => {
    if (!n) {
        n = parseInt(line);
    } else {
        const [x, y] = line.split(' ').map(Number);
        xs.push(x);
        ys.push(y);
        if (xs.length === n) {
            // 处理x方向
            xs.sort((a, b) => a - b);
            const adjustedX = xs.map((x, idx) => x - idx);
            const xCost = calculateMinCost(adjustedX);
            // 处理y方向
            const yCost = calculateMinCost(ys);
            // 总代价
            console.log((xCost + yCost).toString());
            rl.close();
        }
    }
});

内容的提问来源于stack exchange，提问作者Ranjan Kumar