[CSP-J 2025] 座位 题解

题目分析

本题要求将 $n \times m$ 名考生的成绩按由高到低降序排序后，蛇形填入 $n$ 行 $m$ 列的考场中，并求出小 R 所在的座位坐标 $(c, r)$（第 $c$ 列第 $r$ 行）。

蛇形填充规律

按照题目定义：

• 前 $n$ 名考生排在第 $1$ 列，从第 $1$ 行向下排到第 $n$ 行；
• 第 $n+1$ 至 $2n$ 名考生排在第 $2$ 列，从第 $n$ 行向上排到第 $1$ 行；
• 第 $2n+1$ 至 $3n$ 名考生排在第 $3$ 列，从第 $1$ 行向下排到第 $n$ 行；
• $\dots$

总结规律：

1. 奇数列（第 1, 3, 5... 列）：从上往下排，行号依次为 $1 \to n$；
2. 偶数列（第 2, 4, 6... 列）：从下往上排，行号依次为 $n \to 1$。

数学定位公式

假设小 R 的成绩在所有考生（按降序排序）中排名为 $k$（$1 \leq k \leq n \times m$）：

• 列号 $c$：每一列有 $n$ 个座位，因此：$$c = \lfloor \frac{k - 1}{n} \rfloor + 1$$
• 列内相对偏移量：$$p = (k - 1) \bmod n \quad (0 \leq p < n)$$
• 行号 $r$：
  • 若列号 $c$ 为奇数（从上至下）：$r = p + 1$；
  • 若列号 $c$ 为偶数（从下至上）：$r = n - p$。

复杂度分析

• 时间复杂度：排序为 $O(nm \log(nm))$，由于 $n, m \leq 10$，$nm \leq 100$，运算量极小，耗时几乎为 $0$ ms。
• 空间复杂度：$O(nm)$。

参考代码 (C++)

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

using namespace std;

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

    int n, m;
    if (!(cin >> n >> m)) return 0;

    int total = n * m;
    vector<int> a(total);
    for (int i = 0; i < total; ++i) {
        cin >> a[i];
    }

    int my_score = a[0];
    sort(a.begin(), a.end(), greater<int>());

    int rank = 1;
    for (int i = 0; i < total; ++i) {
        if (a[i] == my_score) {
            rank = i + 1;
            break;
        }
    }

    int c = (rank - 1) / n + 1;
    int p = (rank - 1) % n;
    int r = (c % 2 == 1) ? (p + 1) : (n - p);

    cout << c << " " << r << "\n";

    return 0;
}

参考代码 (Python 3)

import sys

def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    n, m = int(input_data[0]), int(input_data[1])
    scores = [int(x) for x in input_data[2:]]
    my_score = scores[0]

    sorted_scores = sorted(scores, reverse=True)
    rank = sorted_scores.index(my_score) + 1

    c = (rank - 1) // n + 1
    p = (rank - 1) % n
    r = (p + 1) if c % 2 == 1 else (n - p)

    print(f"{c} {r}")

if __name__ == "__main__":
    main()