在一个有180人的大班级中,存在两个人生日相同的概率非常大,现给出每个学生的名字,出生月日。试找出所有生日相同的学生。
时间限制:1000
内存限制:65536
输入
第一行为整数n,表示有n个学生,n ≤ 180。此后每行包含一个字符串和两个整数,分别表示学生的名字(名字第一个字母大写,其余小写,不含空格,且长度小于20)和出生月(1 ≤ m ≤ 12)日(1 ≤ d ≤ 31)。名字、月、日之间用一个空格分隔
输出
每组生日相同的学生,输出一行,其中前两个数字表示月和日,后面跟着所有在当天出生的学生的名字,数字、名字之间都用一个空格分隔。对所有的输出,要求按日期从前到后的顺序输出。 对生日相同的名字,按名字从短到长按序输出,长度相同的按字典序输出。如没有生日相同的学生,输出”None”
样例输入
6
Avril 3 2
Candy 4 5
Tim 3 2
Sufia 4 5
Lagrange 4 5
Bill 3 2
样例输出
3 2 Tim Bill Avril
4 5 Candy Sufia Lagrange
https://ask.csdn.net/questions/7997160
【以下回答由 GPT 生成】
解决方案:
1. 创建一个Map,键为生日(月+日),值为一个vector,存储在该生日出生的学生名字。
2. 遍历每个学生的信息,将学生的名字添加到对应生日的vector中。
3. 遍历Map中的每一对键值对,按照日期从小到大的顺序输出生日相同的学生名字。
注意:为了排序和输出的方便,需要使用一个自定义的比较函数来对学生名字进行排序。
以下是C++的代码实现:
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
// 自定义比较函数,用于对学生名字进行排序
bool compare(string a, string b) {
if (a.length() != b.length()) {
return a.length() < b.length();
} else {
return a < b;
}
}
int main() {
int n;
cin >> n;
map<string, vector<string>> birthdayMap;
for (int i = 0; i < n; i++) {
string name;
int month, day;
cin >> name >> month >> day;
string birthday = to_string(month) + " " + to_string(day);
birthdayMap[birthday].push_back(name);
}
bool hasSameBirthday = false;
for (auto it = birthdayMap.begin(); it != birthdayMap.end(); it++) {
if (it->second.size() > 1) {
hasSameBirthday = true;
// 对学生名字按照自定义比较函数进行排序
sort(it->second.begin(), it->second.end(), compare);
// 输出生日相同的学生名字
cout << it->first << " ";
for (int i = 0; i < it->second.size(); i++) {
cout << it->second[i] << " ";
}
cout << endl;
}
}
if (!hasSameBirthday) {
cout << "None" << endl;
}
return 0;
}
复杂度分析: - 时间复杂度:O(nlogn),其中n为学生人数。需要遍历每个学生的信息,将学生名字添加到Map中,而对Map中的键值对按日期进行排序需要O(nlogn)的时间复杂度。 - 空间复杂度:O(n),需要额外的空间来存储Map和每个生日对应的学生名字。
【相关推荐】