C++ 查找生日相同学生：生日悖论算法实现

本程序使用 C++ 语言实现查找一个班级中生日相同的学生，并根据生日日期和姓名进行排序输出。算法基于生日悖论原理，利用 map 和 vector 数据结构进行高效存储和检索。

问题描述

一个大班级中有 n 名学生，存在两个生日相同的概率很高，现在给出每个学生的名字，出生月份和日期，请你编写程序输出所有生日相同的学生。

输入描述

第一行仅仅包含一个正整数 n ，接下来的 n 行，每行描述一名学生的信息，依次为姓名（一个仅含大小写字母长度不超 20 的字符串）、出生的月份和出生日子，出生的月份和日子符合日历的基本规则，各部分两两之间用一个空格分隔。

输出描述

若干行，每行描述一组生日相同的学生信息，各行首先是月，再是日，接下来是这个月日出生的学生的姓名，各部分之间用一个空格分隔。所有输出，按日期从小到大，对于相同生日的同学，先后按照名字的长度从小到大输出，长度相同按照字典序输出，如果所有的输入都没有生日相同的学生，输出“None”。

C++ 代码实现

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

struct Student {
    string name;
    int month;
    int day;
};

bool compare(const Student& s1, const Student& s2) {
    if (s1.month != s2.month) {
        return s1.month < s2.month;
    } else if (s1.day != s2.day) {
        return s1.day < s2.day;
    } else if (s1.name.length() != s2.name.length()) {
        return s1.name.length() < s2.name.length();
    } else {
        return s1.name < s2.name;
    }
}

int main() {
    int n;
    cin >> n;
    vector<Student> students;
    map<pair<int, int>, vector<string>> birthdayMap;
    
    for (int i = 0; i < n; i++) {
        string name;
        int month, day;
        cin >> name >> month >> day;
        students.push_back({name, month, day});
        birthdayMap[{month, day}].push_back(name);
    }
    
    bool found = false;
    for (auto it = birthdayMap.begin(); it != birthdayMap.end(); it++) {
        if (it->second.size() > 1) {
            found = true;
            sort(it->second.begin(), it->second.end(), [](const string& s1, const string& s2) {
                if (s1.length() != s2.length()) {
                    return s1.length() < s2.length();
                } else {
                    return s1 < s2;
                }
            });
            cout << it->first.first << ' ' << it->first.second;
            for (const string& name : it->second) {
                cout << ' ' << name;
            }
            cout << endl;
        }
    }
    
    if (!found) {
        cout << "None" << endl;
    }
    
    return 0;
}

代码解析

数据结构: 使用 vector 存储所有学生信息，使用 map 存储每个生日对应的学生姓名列表，其中 map 的键为 pair<int, int>，表示月份和日期。
输入处理: 读取输入，将学生信息存入 vector 和 map 中。
生日相同判断: 遍历 map，如果某个生日对应学生列表的长度大于 1，则表示存在生日相同的学生。
排序输出: 对生日相同的学生姓名列表进行排序，按照名字长度从小到大，长度相同按字典序输出。最后输出月份、日期和学生姓名。
无生日相同处理: 如果 map 中所有生日对应的学生列表长度都为 1，则表示不存在生日相同的学生，输出“None”。

代码总结

本程序使用 map 和 vector 数据结构实现了高效存储和检索，同时使用 sort 函数进行排序，有效地解决了查找生日相同学生的问题。

优化建议

代码风格: 可以使用更清晰的变量命名和代码注释，提高代码可读性。
错误处理: 可以添加输入验证，确保输入数据合法性。
性能优化: 可以使用更高级的数据结构和算法，例如使用 unordered_map 或 set，进一步提升程序性能。