欢乐赛#54 T4 题解 100% AC

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

// 定义结构体存储学生信息
struct LP {
    string name;  // 学生姓名
    int t;        // LP计数器
} stu[25];        // 最多存储20位不同学生（数组预留空间+5）

int main() {
    string s;     // 临时存储输入的人名
    int i = 0;    // 记录当前已存储的不同学生人数
    
    // 循环读取输入直到遇到"0"
    while (cin >> s) {
        if (s == "0") break;  // 终止条件
        
        bool flag = 0;  // 标记是否已存在该学生记录
        
        // 遍历已有记录检查重复
        for (int j = 1; j <= i; j++) {
            if (stu[j].name == s) {
                stu[j].t++;  // 计数器+1
                flag = 1;    // 标记为已存在
                break;       // 提前结束查找
            }
        }
        
        // 如果是新学生则添加到数组
        if (!flag) {
            i++;                // 学生总数+1
            stu[i].name = s;    // 记录姓名
            stu[i].t = 1;       // 初始化计数器
        }
    }
    
    // 按输入顺序输出结果
    for (int j = 1; j <= i; j++) {
        cout << stu[j].name << " " << stu[j].t << endl;
    }
    
    return 0;
}

关键算法解析

1. 去重统计：使用结构体数组存储首次出现的姓名，后续重复姓名仅增加计数器（时间复杂度$O(n^2)$，因题目限制n≤20可接受）
2. 顺序保持：严格按照首次输入顺序存储和输出，满足题目要求
3. 终止机制：通过检测"0"字符串终止输入循环

复杂度分析

• 空间复杂度：$O(1)$（固定大小数组）
• 时间复杂度：$O(mn)$（m为总输入次数，n为不同姓名数）

输入输出示例解析

以样例输入为例：

Sherry David David Sherry [...] Alexander 0

程序执行流程：

1. 首次遇到"Sherry"存入stu[1]，计数器=1
2. 首次遇到"David"存入stu[2]，计数器=1
3. 再次遇到"David"时找到stu[2]，计数器增至2
4. 最终输出时遍历stu数组，保持原始顺序

该实现严格满足题目要求的：

• 按首次出现顺序输出
• 正确统计重复次数
• 处理最大20个不同学生的限制条件