[CSP-J 2025] 座位

GitHub跳转原题关系图返回列表

统计成绩高于小 R 的人数得到排名，再按列蛇形顺序把排名换算成列号和行号。

OJ: luogu

题目 ID: P14358

难度:普及-

标签:模拟数学

日期: 2026-02-01 17:05

目录

  1. 题意
  2. 思路
    1. 样例理解
  3. 代码
  4. 复杂度
  5. 总结

题意

考场有 n 行 m 列，共 n × m 名考生。所有考生的初赛成绩互不相同，按成绩从高到低分配座位。

分配顺序是按列蛇形：

  • 第 1 列：从第 1 行到第 n 行；
  • 第 2 列：从第 n 行到第 1 行；
  • 第 3 列：再从第 1 行到第 n 行；
  • 以此类推。

输入中 a_1 是小 R 的成绩，要求输出小 R 的座位是第几列第几行。

思路

先看一个可以直接验证想法的朴素解：

cpp
// brute.cpp：小数据暴力解，按成绩排序后模拟蛇形分配座位。
#include <bits/stdc++.h>
using namespace std;

struct Student {
    int score;
    int id;
};

const int MAXN = 105;

int n, m;
Student stu[MAXN];

bool cmp(Student a, Student b) {
    return a.score > b.score;
}

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

    cin >> n >> m;
    int total = n * m;
    for (int i = 1; i <= total; i++) {
        cin >> stu[i].score;
        stu[i].id = i;
    }

    sort(stu + 1, stu + total + 1, cmp);

    for (int rank = 0; rank < total; rank++) {
        if (stu[rank + 1].id != 1) {
            continue;
        }
        int col = rank / n + 1;
        int offset = rank % n;
        int row;
        if (col % 2 == 1) {
            row = offset + 1;
        } else {
            row = n - offset;
        }
        cout << col << ' ' << row << '\n';
        return 0;
    }

    return 0;
}

brute.cpp 把所有考生按成绩从高到低排序，再找到小 R 在排序后的第几个位置。这个位置就是小 R 的排名。

注意这题并不需要真的排序。因为所有成绩互不相同，小 R 前面有多少人，只取决于有多少人的成绩比 a_1 高。

设：

text
rank = 成绩比 a_1 高的人数

这里 rank 是从 0 开始的排名。排名为 0 的人在第一个座位，排名为 1 的人在第二个座位。

因为每一列有 n 个座位，所以：

text
col = rank / n + 1
offset = rank % n

其中 offset 表示小 R 在这一列内部是第几个位置，仍然从 0 开始。

如果 col 是奇数列，这一列从上往下排：

text
row = offset + 1

如果 col 是偶数列，这一列从下往上排：

text
row = n - offset

样例理解

样例 2 中 n=2,m=2n = 2, m = 2，成绩是：

text
98 99 100 97

小 R 的成绩是 98，比他高的有 99, 100 两人，所以 rank=2rank = 2。

于是：

text
col = 2 / 2 + 1 = 2
offset = 2 % 2 = 0

第 2 列是偶数列，从下往上排，所以 row=2−0=2row = 2 - 0 = 2，答案为 2 2。

代码

cpp
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;

int n, m;
int a[MAXN];

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

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

    int better_count = 0; // 成绩比小 R 高的人数，也就是小 R 的 0-based 排名
    for (int i = 2; i <= total; i++) {
        if (a[i] > a[1]) {
            better_count++;
        }
    }

    int col = better_count / n + 1;
    int offset = better_count % n;
    int row;
    if (col % 2 == 1) {
        row = offset + 1;
    } else {
        row = n - offset;
    }

    cout << col << ' ' << row << '\n';
    return 0;
}

复杂度

  • 时间复杂度：O(nm)O(nm)
  • 空间复杂度：O(1)O(1)，除输入数组外只使用常数变量。

总结

本题不要直接模拟整个座位表。先用“比小 R 分数高的人数”得到排名，再把排名换算成蛇形座位坐标即可。