别再暴力搜索了！PTA L1-005 考试座位号的三种高效解法（C语言实现）-编程实验室

别再暴力搜索了！PTA L1-005 考试座位号的三种高效解法（C语言实现）

当面对PTA平台上的L1-005题目时，许多初学者会本能地采用双重循环的暴力搜索方法。这种方法虽然直观易懂，但当数据量达到题目上限（N≤1000）时，其O(n*m)的时间复杂度就显得不够优雅。本文将带你突破思维定式，探索三种更高效的解法，让你在编程竞赛和实际开发中都能游刃有余。

1. 直接映射法：空间换时间的极致

在原始解法中，我们使用结构体数组存储所有考生信息，然后对每个查询都遍历整个数组。这种方法的效率瓶颈在于每次查询都需要O(n)的时间。但仔细观察题目条件，会发现一个关键特性：试机座位号是从1到N的唯一编号。

这个特性让我们可以采取更聪明的存储方式：

#include <stdio.h> #include <string.h> typedef struct { char id[17]; int exam_seat; } Student; int main() { int n, m, test_seat, exam_seat; char id[17]; Student students[1001] = {0}; // 试机座位号作为索引 scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%s %d %d", id, &test_seat, &exam_seat); strcpy(students[test_seat].id, id); students[test_seat].exam_seat = exam_seat; } scanf("%d", &m); while (m--) { scanf("%d", &test_seat); printf("%s %d\n", students[test_seat].id, students[test_seat].exam_seat); } return 0; }

优势分析：

查询时间复杂度降至O(1)
代码更简洁，省去了内层循环
充分利用题目给出的数据特性

注意：这种方法依赖于试机座位号是连续且唯一的条件。如果题目条件变化（如座位号不连续），则需要调整策略。

2. 排序+二分查找：平衡时间与空间的优雅方案

如果题目条件不允许使用直接映射法（比如试机座位号范围远大于实际数量），我们可以考虑先排序再查找的策略。这种方法分为两个阶段：

预处理阶段：按试机座位号排序（O(n log n)）
查询阶段：对每个查询使用二分查找（O(log n) per query）

#include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct { char id[17]; int test_seat; int exam_seat; } Student; int compare(const void *a, const void *b) { return ((Student*)a)->test_seat - ((Student*)b)->test_seat; } int binary_search(Student arr[], int n, int target) { int left = 0, right = n - 1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid].test_seat == target) { return mid; } else if (arr[mid].test_seat < target) { left = mid + 1; } else { right = mid - 1; } } return -1; } int main() { int n, m, tmp; Student students[1000]; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%s %d %d", students[i].id, &students[i].test_seat, &students[i].exam_seat); } qsort(students, n, sizeof(Student), compare); scanf("%d", &m); while (m--) { scanf("%d", &tmp); int idx = binary_search(students, n, tmp); printf("%s %d\n", students[idx].id, students[idx].exam_seat); } return 0; }

性能对比表：

方法	预处理时间	单次查询时间	总时间复杂度	空间复杂度
暴力搜索	O(1)	O(n)	O(m*n)	O(n)
排序+二分	O(n log n)	O(log n)	O(n log n + m log n)	O(n)
直接映射	O(n)	O(1)	O(n + m)	O(max_seat)

3. 简易哈希法：灵活处理非连续编号

当试机座位号范围较大但不连续时，我们可以设计一个简单的哈希函数来优化查询效率。这里展示一种基于取模的哈希实现：

#include <stdio.h> #include <string.h> #define HASH_SIZE 1009 // 选择一个大于1000的质数 typedef struct { char id[17]; int exam_seat; int test_seat; } Student; typedef struct { Student *student; int occupied; } HashEntry; HashEntry hash_table[HASH_SIZE]; int hash_func(int key) { return key % HASH_SIZE; } void insert(int test_seat, char *id, int exam_seat) { int index = hash_func(test_seat); while (hash_table[index].occupied) { index = (index + 1) % HASH_SIZE; // 线性探测 } hash_table[index].student = malloc(sizeof(Student)); strcpy(hash_table[index].student->id, id); hash_table[index].student->exam_seat = exam_seat; hash_table[index].student->test_seat = test_seat; hash_table[index].occupied = 1; } Student* search(int test_seat) { int index = hash_func(test_seat); while (hash_table[index].occupied) { if (hash_table[index].student->test_seat == test_seat) { return hash_table[index].student; } index = (index + 1) % HASH_SIZE; } return NULL; } int main() { int n, m, test_seat, exam_seat; char id[17]; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%s %d %d", id, &test_seat, &exam_seat); insert(test_seat, id, exam_seat); } scanf("%d", &m); while (m--) { scanf("%d", &test_seat); Student *s = search(test_seat); printf("%s %d\n", s->id, s->exam_seat); } // 释放内存 for (int i = 0; i < HASH_SIZE; i++) { if (hash_table[i].occupied) { free(hash_table[i].student); } } return 0; }

哈希法关键点：