使每位学生都有座位的最少移动次数 图解题解

两排乱序位置，怎么配座位最省

给两个长度都是 n 的数组：seats 里是每个座位的位置，students 里是每名学生的位置。每次能把某名学生的位置加一或减一，走一格算一次移动。要让每名学生都坐上一个座位、且没有两人挤同一个座位，问最少一共挪多少格。题面例子 seats=[3,1,5]、students=[2,7,4]，答案是 4。位置允许重复。

先想清楚该让谁去坐哪个座位

n 名学生配 n 个座位，能排的配法有 n 的阶乘种，挨个试到 n 稍大就算不完。而且两个数组给进来都是乱的，照原始下标硬配也不对——例子里第 2 个座位在 1、第 2 个学生在 7，这一对就得跑 6 格，三对加起来 8 格，并不是最少。真正要定的是哪名学生去坐哪个座位，才能把总格数压到最小。

为什么两边排好序、同名次配对就最省

把两排位置各自从小到大排好，然后第 1 小的座位配第 1 小的学生、第 2 小配第 2 小，一路对下去。这样为什么最省？假设某个更优的配法里出现了交叉：一个较小的座位配了较大的学生、一个较大的座位配了较小的学生。把这两名学生的座位对调一下，让小的配小、大的配大，算一下这两对的绝对差之和只会变小或持平，绝不会变大。既然任何交叉都能这样捋直而不吃亏，一路对调下去，最优配法一定收敛成两边同序配对的样子。

配好之后每对怎么算，哪里最容易写错

配对定死后，一名学生从原位挪到座位，走的格数就是两个位置之差的绝对值，把 n 对的绝对差全加起来就是答案。几个地方容易写反：只排一边不行，座位排了、学生没排，名次照样对不齐，配出来还是交叉的；别拿位置的和或平方去算花费，一次移动只改一格，走的格数就是起点终点的绝对差；位置有重复也不用特判，照排照配，绝对差对重复值天然成立。

题面这组数，最少 4 格是怎么配出来的

两排各自排序：座位排成 1、3、5，学生排成 2、4、7。同名次配对：座位 1 配学生 2，差 1；座位 3 配学生 4，差 1；座位 5 配学生 7，差 2。三对相加 1 加 1 加 2，得到 4。

两次排序各是 O(n log n)，后面配对累加只多一趟线性扫，合起来 O(n log n)；除排序外只用一个累计变量，空间 O(1)。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:
        seats.sort()
        students.sort()
        return sum(abs(a - b) for a, b in zip(seats, students))

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int minMovesToSeat(vector<int>& seats, vector<int>& students) {
        sort(seats.begin(), seats.end());
        sort(students.begin(), students.end());
        int ans = 0;
        for (int i = 0; i < seats.size(); ++i) {
            ans += abs(seats[i] - students[i]);
        }
        return ans;
    }
};

Java

import java.util.*;
class Solution {
    public int minMovesToSeat(int[] seats, int[] students) {
        Arrays.sort(seats);
        Arrays.sort(students);
        int ans = 0;
        for (int i = 0; i < seats.length; ++i) {
            ans += Math.abs(seats[i] - students[i]);
        }
        return ans;
    }
}