题目描述

在一所重点大学举办的开源展览会上，各个开源项目的负责人将报名表贴在墙上，并在顶部用大写字母标出项目名称以便识别。学生使用自己的用户ID报名参加项目（用户ID是一个以小写字母和数字组成的字符串，且必须以字母开头）。活动组织者随后将所有报名表从墙上取下并录入信息。

任务要求：

1. 统计每个项目的有效报名学生人数（每个学生在一个项目中多次报名只算一次）。
2. 如果一个学生报名了多个项目，则该学生不计入任何项目的统计。
3. 输出每个项目的名称和有效报名人数，按人数降序排列。如果人数相同，按项目名称的字典序升序排列。

输入格式：

• 多个测试用例，每个测试用例以一行 1 结束。
• 最后一个测试用例后跟着一行 0 表示输入结束。
• 每个测试用例包含多个项目的报名表：
  • 项目名称（一行大写字母开头）。
  • 学生ID（每行一个，以小写字母开头）。

输出格式：

• 每个测试用例的输出包含若干行，每行格式为 项目名称 人数。
• 按人数降序排列，人数相同则按项目名称字典序升序排列。

解题思路

1. 数据存储

• studentToProject：记录每个学生报名的项目（map<string, string>）。
  • 如果学生报名多个项目，标记为无效（""）。
• projectToStudents：记录每个项目的有效学生集合（map<string, set<string>>）。
  • 使用 set 自动去重，避免重复计数。

2. 处理逻辑

1. 读取输入：

   • 逐行读取输入，遇到 1 结束当前测试用例，遇到 0 结束程序。
   • 如果是大写字母开头的行，认为是新项目。
   • 如果是小写字母开头的行，认为是学生ID，检查是否已报名其他项目。

2. 标记无效学生：

   • 如果学生已报名其他项目，则标记该学生为无效（studentToProject[student] = ""）。

3. 统计有效学生：

   • 遍历 studentToProject，将只报名一个项目的学生加入对应项目的 set 中。

4. 排序输出：

   • 将 projectToStudents 转换为 vector<Project>，按题目要求排序（人数降序，名称升序）。
   • 输出结果。

3. 关键点

• 去重：使用 set 存储学生ID，自动处理重复报名。
• 无效学生处理：报名多个项目的学生不计入任何项目。
• 排序规则：自定义 compareProjects 函数实现题目要求的排序。

代码实现（C++）

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
using namespace std;

struct Project {
	string name;
	int count;
};

bool compareProjects(const Project &a, const Project &b) {
	if (a.count != b.count) {
		return a.count > b.count;
	} else {
		return a.name < b.name;
	}
}

int main() {
	string line;
	while (getline(cin, line)) {
		if (line == "0") break;
		
		map<string, string> studentToProject;  // 记录学生报名的项目
		map<string, set<string> > projectToStudents;  // 注意这里的空格 > >
		
		string currentProject;
		while (line != "1") {
			if (isupper(line[0])) {  // 新项目
				currentProject = line;
				projectToStudents[currentProject] = set<string>();
			} else {  // 学生ID
				string student = line;
				// 检查学生是否已经报名其他项目
				if (studentToProject.count(student)) {
					if (studentToProject[student] != currentProject) {
						// 学生报名了多个项目，标记为无效
						studentToProject[student] = "";
					}
				} else {
					studentToProject[student] = currentProject;
				}
			}
			getline(cin, line);
		}
		
		// 重新统计每个项目的有效学生数
		for (map<string, string>::iterator it = studentToProject.begin(); 
			it != studentToProject.end(); ++it) {
			string student = it->first;
			string project = it->second;
			if (!project.empty()) {
				projectToStudents[project].insert(student);
			}
		}
		
		// 转换为Project结构并排序
		vector<Project> projects;
		for (map<string, set<string> >::iterator it = projectToStudents.begin();
			it != projectToStudents.end(); ++it) {
			Project p;
			p.name = it->first;
			p.count = it->second.size();
			projects.push_back(p);
		}
		sort(projects.begin(), projects.end(), compareProjects);
		
		// 输出结果
		for (vector<Project>::iterator it = projects.begin();
			it != projects.end(); ++it) {
			cout << it->name << " " << it->count << endl;
		}
	}
	return 0;
}

示例分析

输入：

UBQTS TXT
tthumb
LIVESPACE BLOGJAM
philton
aeinstein
YOUBOOK
j97lee
sswxyzy
j97lee
aeinstein
SKINUX
1
0

处理过程：

1. aeinstein 报名了 LIVESPACE BLOGJAM 和 YOUBOOK，因此无效。
2. j97lee 重复报名 YOUBOOK，只计一次。
3. SKINUX 无有效报名。

输出：

YOUBOOK 2       // j97lee, sswxyzy
LIVESPACE BLOGJAM 1  // philton
UBQTS TXT 1     // tthumb
SKINUX 0        // 无有效报名

复杂度分析

• 时间复杂度：O(N log N)，其中 N 是学生或项目的数量（主要来自 map 和 sort 操作）。
• 空间复杂度：O(N + M)，存储学生和项目信息。