电影院座位优先级排序应如何选择排序算法？

2026-11-04技术老齐

优先使用 `std::sort`

这道题可以直接用 C++ 标准库的 std::sort：将所有座位按“距离平方、排号、座位号”依次升序排序，再按排序位置分配优先级。

设座位总数为 (N=R\times W)，最多有：

[ 500\times501=250500 ]

个座位。在这个规模下，(O(N\log N)) 的排序方法效率合适，实现也简单。题目没有给出时间和内存限制，无法断言哪种实现实际耗时最短，std::sort 可以作为首选。

这道题没有必要手写 quicksort。另外，“分治”（divide and conquer）是一种算法设计思想，快速排序和归并排序都使用了它，因此不能把分治与具体的排序算法并列比较。

把优先级规则写成排序键

设排号为 (r)，座位号为 (c)，均从 1 开始。第一排中央座位的列号为：

[ m=\frac{W+1}{2} ]

横向和纵向的相邻座位间距相同，可以将间距视为 1。座位到最佳座位的距离为：

[ d=\sqrt{(r-1)^2+(c-m)^2} ]

比较距离时，直接比较距离平方即可：

[ d^2=(r-1)^2+(c-m)^2 ]

平方根函数在非负数上严格递增，因此比较距离平方不会改变排序结果，还能省去开平方和浮点数比较。

每个座位的完整排序键为：

(distance_squared, row, column)

按字典序升序比较：

距离平方较小的座位在前。
距离相同时，排号较小的座位在前。
距离和排号都相同时，座位号较小的座位在前。

例如，W = 7 时，第一排中央座位是 (1, 4)。与它距离平方为 1 的座位按以下顺序排列：

(1, 3)、(1, 5)、(2, 4)

它们的优先级分别为 2、3、4。

实现步骤

枚举所有座位，保存距离平方、排号和座位号。
调用 std::sort，按完整排序键排序。
遍历排序结果，把第 (i) 个座位的优先级设为 (i+1)。
将优先级写回二维数组。
按排号从 (R) 到 1 输出，每排仍按座位号从 1 到 (W) 输出。

输出需要保留座位布局，因此要将排序得到的优先级写回对应坐标。

C++ 代码示例

#include <algorithm>
#include <iostream>
#include <tuple>
#include <vector>

struct Seat {
    long long distanceSquared;
    int row;
    int column;
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int W, R;
    if (!(std::cin >> W >> R)) {
        return 0;
    }

    const int middle = (W + 1) / 2;

    std::vector<Seat> seats;
    seats.reserve(W * R);

    for (int row = 1; row <= R; ++row) {
        for (int column = 1; column <= W; ++column) {
            const long long dr = row - 1;
            const long long dc = column - middle;

            seats.push_back({
                dr * dr + dc * dc,
                row,
                column
            });
        }
    }

    std::sort(seats.begin(), seats.end(),
              [](const Seat& a, const Seat& b) {
                  return std::tie(a.distanceSquared, a.row, a.column)
                       < std::tie(b.distanceSquared, b.row, b.column);
              });

    std::vector<std::vector<int>> priority(
        R + 1, std::vector<int>(W + 1)
    );

    int nextPriority = 1;
    for (const Seat& seat : seats) {
        priority[seat.row][seat.column] = nextPriority++;
    }

    for (int row = R; row >= 1; --row) {
        for (int column = 1; column <= W; ++column) {
            if (column > 1) {
                std::cout << ' ';
            }
            std::cout << priority[row][column];
        }
        std::cout << '\n';
    }

    return 0;
}

输入：

7 4

输出：

27 25 21 18 22 26 28
23 14 12 9 13 15 24
19 10 5 4 6 11 20
16 7 2 1 3 8 17

枚举和回填各需要 (O(N)) 时间，排序需要 (O(N\log N)) 时间，总时间复杂度为 (O(N\log N))。座位列表与结果矩阵共占用 (O(N)) 空间。

为什么不需要稳定排序？

稳定排序会保留排序键相等的元素的原有顺序。本题的排序键包含排号和座位号，不同座位的完整排序键不会相同，因此 std::sort 就能确定唯一顺序。

如果只比较距离，就需要另行保证同距离座位的排号和座位号顺序。例如，先按排号、座位号递增枚举，再按距离进行稳定排序。直接使用完整排序键更容易检查，也不依赖枚举顺序。

比较器必须使用严格比较。代码中的 < 不能改成 <=，否则会违反 std::sort 对比较器的要求。

能不能使用计数排序或桶排序？

可以。本题的距离平方是非负整数，最大值为：

[ (R-1)^2+\left(\frac{W-1}{2}\right)^2 \le499^2+250^2=311501 ]

可以按距离平方建立桶：

按排号递增、座位号递增枚举座位，依次追加到对应桶中。
从距离平方最小的桶开始遍历。
同一桶内保持追加顺序，依次分配优先级。

这样，同距离的座位也能满足排号和座位号的排序规则。设最大距离平方为 (D)，时间复杂度和空间复杂度均为 (O(N+D))。

桶的初始化、存储方式和内存开销都会影响实际性能。当前数据规模下，std::sort 的代码更直接。如果时间限制或实际测量表明需要优化，再进一步比较桶方案。

其他问题该如何选择排序方法？

先确定需要什么结果，再结合数据规模、键值范围和内存限制选择。

问题条件	常见选择	选择依据
需要完整排序，比较规则较一般	标准库排序，如 `std::sort`	实现简短，通常可作为默认方案
相同键必须保留原有顺序	`std::stable_sort`	需要稳定性
整数键范围较小	计数排序或桶方法	可做到 (O(N+K))，但要考虑键值范围 (K) 的存储成本
只需要最小的 (k) 个元素	堆、`std::partial_sort`	可以避免把全部元素完整排序
只需要第 (k) 小的元素或划分	`std::nth_element`	无须得到所有元素的有序结果
数据很少，或已有序程度很高	可考虑插入排序	小规模下开销低，接近有序时移动次数较少
数据无法全部装入内存	外部归并排序	需要控制磁盘读写和内存占用

手写 quicksort 需要处理枢轴选择、重复元素和递归深度等问题，朴素实现的最坏时间复杂度可能退化到 (O(N^2))。除非题目要求实现排序算法，或有标准库无法满足的具体约束，通常可以先使用标准库。

这道座位题需要重点检查排序键是否完整，以及输出顺序是否符合题意。