C语言实战：构建与输出高效、可排序的ACM竞赛榜单25

在编程竞赛，尤其是ACM/ICPC（国际大学生程序设计竞赛）这类团队竞赛中，实时且准确的榜单（Scoreboard）是比赛的核心组成部分。它不仅反映了各支队伍的即时表现，更是驱动选手奋力拼搏的动力源泉。对于程序员而言，理解并能用C语言实现一个功能完善的ACM榜单系统，无疑是深入理解数据结构、算法和C语言底层操作的绝佳实践。

C语言以其卓越的性能、对内存的精细控制以及广泛的应用场景，成为实现这类系统（尤其是在对效率有较高要求的场合）的强大工具。本文将从ACM榜单的基本构成出发，逐步讲解如何利用C语言构建一个能够读取数据、进行排名并输出美观榜单的程序。我们将涵盖数据结构设计、文件输入输出、核心排序算法以及友好的榜单格式化输出。

一、理解ACM榜单的核心构成与计分规则

一个典型的ACM竞赛榜单，需要展示以下核心信息：
队伍信息：队名、学校。
题目信息：通常有A、B、C…等多道题目。每道题目会记录队伍的尝试次数和是否通过（Accepted, AC）状态。
通过题数 (Solved Problems)：队伍成功解决的题目数量。
总罚时 (Penalty Time)：根据队伍解决题目所花费的时间和错误提交次数计算。

ACM计分规则（简化版）：
排名依据：首先，通过题数多的队伍排名靠前。
罚时作为次要依据：如果通过题数相同，则总罚时少的队伍排名靠前。
罚时计算：

每道通过的题目，其罚时为“从比赛开始到首次AC提交的时间（分钟）” + “该题首次AC前所有错误提交次数 * 20分钟”。
未通过的题目不计罚时。
总罚时是所有通过题目的罚时之和。

理解这些规则是设计数据结构和实现排序算法的基础。

二、数据结构设计：C语言的基石

为了有效地存储和管理榜单数据，我们需要设计合适的C语言结构体（struct）。我们将定义两个主要的结构体：一个用于记录每道题目的状态，另一个用于记录每支队伍的整体信息。

1. 题目状态结构体 (ProblemStatus)

每道题目对于每支队伍都有一个状态，包括尝试次数、通过时间等。我们假设题目数量是固定的（例如，10道题）。#define MAX_PROBLEMS 10 // 最大题目数量
typedef struct {
int attempts; // 尝试次数
int solved_time; // 首次AC的时间（分钟），如果未AC则为0
int is_solved; // 是否已AC (1:是, 0:否)
} ProblemStatus;

2. 队伍信息结构体 (Team)

这个结构体将包含一支队伍的所有相关信息，并嵌入了ProblemStatus数组。#define MAX_NAME_LEN 50 // 队名最大长度
#define MAX_TEAMS 100 // 最大队伍数量（可根据需要动态调整）
typedef struct {
char name[MAX_NAME_LEN]; // 队名
int solved_problems; // 通过题目数
int penalty_time; // 总罚时
ProblemStatus problems[MAX_PROBLEMS]; // 每道题的状态
} Team;
// 为了处理不确定数量的队伍，我们通常会使用动态数组
// Team *teams;
// int num_teams;

三、数据录入与初始化：文件输入

对于大规模的竞赛，手动输入数据显然不切实际。从文件读取数据是更标准且高效的做法。我们将设计一个简单的文本文件格式来存储队伍的比赛数据。例如，每行代表一个队伍，包含其队名及每道题的提交情况。

示例数据文件 () 格式：Team_Alpha 0,0,0,0,0,0,0,0,0,0
Team_Beta 1,30,0,0,1,60,2,80,0,0,0,0,0,0,0,0,0,0
Team_Gamma 1,45,1,70,0,0,0,0,0,0,0,0,0,0,0,0,0,0
Team_Delta 1,20,1,40,1,90,0,0,0,0,0,0,0,0,0,0,0,0

解释：每行格式为 `队名 (attempts1,time1,solved1) (attempts2,time2,solved2) ...`。为了简化文件解析，我们可能将其设计为：`Team_Name solved_problems penalty problem_A_attempts problem_A_time problem_A_solved ...`。但更实际的情况是，我们只有提交记录，需要程序来计算出 `solved_problems` 和 `penalty`。

更实际的输入格式设计（假设每行代表一个队伍，题目状态以 `attempts,time,solved` 对的形式出现）：Team_Alpha 0,0,0 0,0,0 0,0,0 0,0,0 0,0,0 0,0,0 0,0,0 0,0,0 0,0,0 0,0,0
Team_Beta 1,30,1 0,0,0 1,60,1 2,80,1 0,0,0 0,0,0 0,0,0 0,0,0 0,0,0 0,0,0
Team_Gamma 1,45,1 1,70,1 0,0,0 0,0,0 0,0,0 0,0,0 0,0,0 0,0,0 0,0,0 0,0,0
Team_Delta 1,20,1 1,40,1 1,90,1 0,0,0 0,0,0 0,0,0 0,0,0 0,0,0 0,0,0 0,0,0

这样，每个队伍的题目数据是固定的 `MAX_PROBLEMS` 组 `attempts,time,solved`。

文件读取函数示例：#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// ... (ProblemStatus 和 Team 结构体定义) ...
// 计算队伍的罚时和通过题数
void calculate_team_stats(Team *team) {
team->solved_problems = 0;
team->penalty_time = 0;
for (int i = 0; i < MAX_PROBLEMS; i++) {
if (team->problems[i].is_solved) {
team->solved_problems++;
team->penalty_time += team->problems[i].solved_time;
// 每次错误提交增加20分钟罚时
team->penalty_time += (team->problems[i].attempts - 1) * 20;
}
}
}
// 从文件读取队伍数据
int read_teams_from_file(const char *filename, Team teams[], int max_teams) {
FILE *fp = fopen(filename, "r");
if (fp == NULL) {
perror("Error opening file");
return -1;
}
int num_teams = 0;
char line[512]; // 假设一行数据不会超过512字符
while (fgets(line, sizeof(line), fp) != NULL && num_teams < max_teams) {
// 移除行尾的换行符
line[strcspn(line, "")] = 0;

Team *current_team = &teams[num_teams];
char *token;

// 读取队名
token = strtok(line, " ");
if (token == NULL) continue;
strncpy(current_team->name, token, MAX_NAME_LEN - 1);
current_team->name[MAX_NAME_LEN - 1] = '\0'; // 确保字符串以空字符结尾
// 读取每道题目的状态
for (int i = 0; i < MAX_PROBLEMS; i++) {
token = strtok(NULL, ","); // attempts
if (token == NULL) break;
current_team->problems[i].attempts = atoi(token);
token = strtok(NULL, ","); // solved_time
if (token == NULL) break;
current_team->problems[i].solved_time = atoi(token);
token = strtok(NULL, " "); // is_solved (这里使用空格作为分隔符来分离下一组题目数据)
if (token == NULL) break;
current_team->problems[i].is_solved = atoi(token);
}

calculate_team_stats(current_team); // 计算当前队伍的通过题数和总罚时
num_teams++;
}
fclose(fp);
return num_teams;
}

注意：上述strtok的用法在一个循环中处理多种分隔符（逗号和空格）需要非常小心。更健壮的文件解析可能需要更复杂的逻辑，例如先用空格分隔队名和题目串，再用逗号分隔题目串内部。

四、核心算法：榜单排序

C语言标准库提供了强大的通用排序函数 qsort()。我们只需要提供一个比较函数，它就能帮助我们对任意类型的数组进行排序。

1. qsort() 函数原型

void qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *));
base: 指向待排序数组的第一个元素的指针。
nmemb: 数组中元素的数量。
size: 数组中每个元素的大小（以字节为单位）。
compar: 指向比较函数的指针，该函数定义了排序规则。

2. 比较函数 (compareTeams)

比较函数接收两个 void* 类型的指针，需要将其转换为我们自定义的结构体指针，然后根据ACM排名规则进行比较：int compareTeams(const void *a, const void *b) {
const Team *teamA = (const Team *)a;
const Team *teamB = (const Team *)b;
// 1. 通过题数多的优先
if (teamA->solved_problems != teamB->solved_problems) {
return teamB->solved_problems - teamA->solved_problems; // 降序
}
// 2. 通过题数相同，罚时少的优先
if (teamA->penalty_time != teamB->penalty_time) {
return teamA->penalty_time - teamB->penalty_time; // 升序
}
// 3. 通过题数和罚时都相同，按队名字典序（升序）排列 (可选，通常不严格要求)
return strcmp(teamA->name, teamB->name);
}

在 main 函数中，调用 qsort 即可对队伍数组进行排序：qsort(teams, num_teams, sizeof(Team), compareTeams);

五、榜单输出：格式化与美观

一个清晰、易读的榜单对于用户体验至关重要。我们将使用 printf 函数进行格式化输出，以表格形式展示队伍信息和题目状态。void print_scoreboard(const Team teams[], int num_teams) {
printf("--------------------------------------------------------------------------------------------------------------------------------");
printf("| %-4s | %-20s | %-6s | %-8s |", "Rank", "Team Name", "Solved", "Penalty");
for (int i = 0; i < MAX_PROBLEMS; i++) {
printf(" %-4c |", 'A' + i); // 题目编号 A, B, C...
}
printf("");
printf("--------------------------------------------------------------------------------------------------------------------------------");
for (int i = 0; i < num_teams; i++) {
printf("| %-4d | %-20s | %-6d | %-8d |", i + 1, teams[i].name, teams[i].solved_problems, teams[i].penalty_time);
for (int j = 0; j < MAX_PROBLEMS; j++) {
if (teams[i].problems[j].is_solved) {
// 如果是AC，显示 + (尝试次数)
printf(" +%-3d |", teams[i].problems[j].attempts);
} else if (teams[i].problems[j].attempts > 0) {
// 如果有尝试但未AC，显示 - (尝试次数)
printf(" -%-3d |", teams[i].problems[j].attempts);
} else {
// 未尝试
printf(" %-4s |", ""); // 空白
}
}
printf("");
}
printf("--------------------------------------------------------------------------------------------------------------------------------");
}

解释格式化字符串：

%-4s：左对齐，占用4个字符宽度的字符串。
%-20s：左对齐，占用20个字符宽度的字符串。
%-6d：左对齐，占用6个字符宽度的整数。
`+%-3d`：显示正负号，左对齐，占用3个字符宽度的整数。

六、完整代码实现

将上述所有部分整合，我们将得到一个完整的C语言ACM榜单程序。为了实现动态队伍数量，我们将使用malloc和realloc。#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_PROBLEMS 10 // 最大题目数量
#define MAX_NAME_LEN 50 // 队名最大长度
#define INITIAL_MAX_TEAMS 10 // 初始最大队伍数量
// 题目状态结构体
typedef struct {
int attempts; // 尝试次数
int solved_time; // 首次AC的时间（分钟），如果未AC则为0
int is_solved; // 是否已AC (1:是, 0:否)
} ProblemStatus;
// 队伍信息结构体
typedef struct {
char name[MAX_NAME_LEN]; // 队名
int solved_problems; // 通过题目数
int penalty_time; // 总罚时
ProblemStatus problems[MAX_PROBLEMS]; // 每道题的状态
} Team;
// 计算队伍的罚时和通过题数
void calculate_team_stats(Team *team) {
team->solved_problems = 0;
team->penalty_time = 0;
for (int i = 0; i < MAX_PROBLEMS; i++) {
if (team->problems[i].is_solved) {
team->solved_problems++;
team->penalty_time += team->problems[i].solved_time;
// 每次错误提交增加20分钟罚时
team->penalty_time += (team->problems[i].attempts - 1) * 20;
}
}
}
// 从文件读取队伍数据
// 返回实际读取的队伍数量，-1表示文件打开失败
int read_teams_from_file(const char *filename, Team teams_ptr, int *current_max_teams) {
FILE *fp = fopen(filename, "r");
if (fp == NULL) {
perror("Error opening file");
return -1;
}
int num_teams = 0;
char line[1024]; // 假设一行数据不会超过1024字符
*teams_ptr = (Team *)malloc(sizeof(Team) * (*current_max_teams));
if (*teams_ptr == NULL) {
perror("Memory allocation failed");
fclose(fp);
return -1;
}
while (fgets(line, sizeof(line), fp) != NULL) {
// 如果当前队伍数量达到最大容量，则重新分配内存
if (num_teams == *current_max_teams) {
*current_max_teams *= 2; // 容量翻倍
Team *temp_teams = (Team *)realloc(*teams_ptr, sizeof(Team) * (*current_max_teams));
if (temp_teams == NULL) {
perror("Memory re-allocation failed");
free(*teams_ptr);
fclose(fp);
return -1;
}
*teams_ptr = temp_teams;
}
// 移除行尾的换行符
line[strcspn(line, "")] = 0;

Team *current_team = &((*teams_ptr)[num_teams]);
char *token;
char *rest_of_line = line;
// 读取队名 (使用空格作为分隔符)
token = strtok_r(rest_of_line, " ", &rest_of_line); // strtok_r 是线程安全的版本
if (token == NULL) continue; // 空行或格式错误
strncpy(current_team->name, token, MAX_NAME_LEN - 1);
current_team->name[MAX_NAME_LEN - 1] = '\0'; // 确保字符串以空字符结尾
// 读取每道题目的状态
for (int i = 0; i < MAX_PROBLEMS; i++) {
// 格式: attempts,time,solved
char *sub_token;

// attempts
token = strtok_r(rest_of_line, ",", &rest_of_line);
if (token == NULL) { // 数据不足，填充默认值并中断
current_team->problems[i].attempts = 0;
current_team->problems[i].solved_time = 0;
current_team->problems[i].is_solved = 0;
continue;
}
current_team->problems[i].attempts = atoi(token);
// solved_time
token = strtok_r(rest_of_line, ",", &rest_of_line);
if (token == NULL) {
current_team->problems[i].solved_time = 0;
current_team->problems[i].is_solved = 0;
continue;
}
current_team->problems[i].solved_time = atoi(token);

// is_solved (这里使用空格作为分隔符来分离下一组题目数据或行尾)
token = strtok_r(rest_of_line, " ", &rest_of_line);
if (token == NULL) {
current_team->problems[i].is_solved = 0;
continue;
}
current_team->problems[i].is_solved = atoi(token);
}

calculate_team_stats(current_team); // 计算当前队伍的通过题数和总罚时
num_teams++;
}
fclose(fp);
// 如果实际队伍数量小于分配的最大容量，可以缩小内存，但对于小规模程序通常非必要
if (num_teams < *current_max_teams) {
Team *temp_teams = (Team *)realloc(*teams_ptr, sizeof(Team) * num_teams);
if (temp_teams != NULL) {
*teams_ptr = temp_teams;
*current_max_teams = num_teams;
}
}
return num_teams;
}
// 比较函数，用于qsort
int compareTeams(const void *a, const void *b) {
const Team *teamA = (const Team *)a;
const Team *teamB = (const Team *)b;
// 1. 通过题数多的优先 (降序)
if (teamA->solved_problems != teamB->solved_problems) {
return teamB->solved_problems - teamA->solved_problems;
}
// 2. 通过题数相同，罚时少的优先 (升序)
if (teamA->penalty_time != teamB->penalty_time) {
return teamA->penalty_time - teamB->penalty_time;
}
// 3. 通过题数和罚时都相同，按队名字典序（升序）排列 (可选)
return strcmp(teamA->name, teamB->name);
}
// 打印榜单
void print_scoreboard(const Team teams[], int num_teams) {
printf("--------------------------------------------------------------------------------------------------------------------------------");
printf("| %-4s | %-20s | %-6s | %-8s |", "Rank", "Team Name", "Solved", "Penalty");
for (int i = 0; i < MAX_PROBLEMS; i++) {
printf(" %-4c |", 'A' + i); // 题目编号 A, B, C...
}
printf("");
printf("--------------------------------------------------------------------------------------------------------------------------------");
for (int i = 0; i < num_teams; i++) {
printf("| %-4d | %-20s | %-6d | %-8d |", i + 1, teams[i].name, teams[i].solved_problems, teams[i].penalty_time);
for (int j = 0; j < MAX_PROBLEMS; j++) {
if (teams[i].problems[j].is_solved) {
// 如果是AC，显示 + (尝试次数)
printf(" +%-3d |", teams[i].problems[j].attempts);
} else if (teams[i].problems[j].attempts > 0) {
// 如果有尝试但未AC，显示 - (尝试次数)
printf(" -%-3d |", teams[i].problems[j].attempts);
} else {
// 未尝试
printf(" %-4s |", ""); // 空白
}
}
printf("");
}
printf("--------------------------------------------------------------------------------------------------------------------------------");
}
int main() {
Team *teams = NULL;
int num_teams = 0;
int current_max_teams = INITIAL_MAX_TEAMS;
const char *filename = ""; // 数据文件名
// 尝试读取数据
num_teams = read_teams_from_file(filename, &teams, ¤t_max_teams);
if (num_teams == -1) {
fprintf(stderr, "Failed to read data from %s. Exiting.", filename);
return 1;
}
if (num_teams == 0) {
printf("No team data found in %s.", filename);
// 即使没有队伍，也要释放可能的初始分配
if (teams != NULL) free(teams);
return 0;
}
printf("Successfully read %d teams from %s.", num_teams, filename);
// 排序
qsort(teams, num_teams, sizeof(Team), compareTeams);
// 打印榜单
print_scoreboard(teams, num_teams);
// 释放动态分配的内存
free(teams);
teams = NULL; // 避免悬空指针
return 0;
}

示例文件内容：Team_Alpha 1,30,1 1,70,1 1,120,1 0,0,0 0,0,0 0,0,0 0,0,0 0,0,0 0,0,0 0,0,0
Team_Beta 1,20,1 2,50,1 0,0,0 0,0,0 0,0,0 0,0,0 0,0,0 0,0,0 0,0,0 0,0,0
Team_Gamma 2,40,1 1,60,1 1,100,1 1,150,1 0,0,0 0,0,0 0,0,0 0,0,0 0,0,0 0,0,0
Team_Delta 1,25,1 1,80,1 2,110,0 0,0,0 0,0,0 0,0,0 0,0,0 0,0,0 0,0,0 0,0,0
Team_Epsilon 0,0,0 0,0,0 0,0,0 1,60,1 0,0,0 0,0,0 0,0,0 0,0,0 0,0,0 0,0,0
Team_Zeta 3,35,1 0,0,0 0,0,0 0,0,0 0,0,0 0,0,0 0,0,0 0,0,0 0,0,0 0,0,0

七、进阶功能与扩展思考

当前的实现是一个基础的、功能完备的榜单系统，但仍然有许多可以改进和扩展的地方：
更健壮的文件解析：目前的 strtok_r 处理假设输入格式严格。实际中可能需要更多的错误检查，例如验证数值是否合法，处理缺省值等。
动态题目数量：如果题目数量不是固定的 MAX_PROBLEMS，可以在 Team 结构体中使用指向 ProblemStatus 数组的指针，并根据实际题目数量动态分配内存。
实时更新：对于实际比赛，榜单需要实时更新。这可能涉及文件监听、网络通信（例如从裁判系统获取提交数据）、多线程处理等更复杂的机制。
持久化：将榜单数据存储到数据库（如SQLite）或更复杂的二进制文件中，以便更高效地查询和管理。
用户界面：当前的输出是命令行文本界面。可以考虑使用C语言的GUI库（如GTK+或Qt，尽管通常C++更常用）或通过Web后端（如CGI）展示更丰富的图形界面。
错误处理：增加对 malloc/realloc 失败、文件读写错误等情况的详细错误报告和优雅退出机制。
性能优化：对于海量队伍和提交记录，可能需要考虑更高效的排序算法（例如基数排序如果数据范围允许），或者针对榜单特性的增量更新算法。