2172 生日相同
大约 3 分钟
2172 生日相同
【算法】 排序、枚举、分组
【C++】 sort、结构体、string、vector
【难度】 入门
一、题目简述
有 个学生(),给出每个人的名字和出生月日。找出所有生日相同的学生(同月同日),按日期从前到后输出。如果没有生日相同的人,输出 None。
对同一天生日的人,按名字从短到长输出,长度相同的按字典序输出。
二、解题思路
2.1 核心思路:按日期分组
- 把所有学生按**(月, 日)**分组
- 对于每组人数 ≥ 2 的日期,按规则输出
- 如果所有日期组都只有 1 人,输出
None
2.2 实现方法
方法一:排序后扫描
- 给每个学生记录名字、月、日
- 按 (月, 日) 排序,同日期的人会相邻
- 扫描排序后的数组,找出连续同日期的人
- 对每组同日期的人,按名字规则排序后输出
方法二:枚举每一天
用 vector<string> group[13][32] 记录每个月日的学生名单。
这里推荐排序后扫描的方法,更易理解。
2.3 排序规则设计
需要两次排序:
第一次:按日期排序(月升序,日升序),让同日期的人聚在一起。
bool cmpByDate(Student a, Student b) {
if (a.month != b.month)
return a.month < b.month;
return a.day < b.day;
}第二次:同日期内按名字排序(长度升序,字典序升序)。
bool cmpByName(Student a, Student b) {
if (a.name.length() != b.name.length())
return a.name.length() < b.name.length();
return a.name < b.name;
}2.4 手动模拟
输入:
6
Avril 3 2
Candy 4 5
Tim 3 2
Sufia 4 5
Lagrange 4 5
Bill 3 2按日期排序后:
| 月 | 日 | 名字 |
|---|---|---|
| 3 | 2 | Avril |
| 3 | 2 | Tim |
| 3 | 2 | Bill |
| 4 | 5 | Candy |
| 4 | 5 | Sufia |
| 4 | 5 | Lagrange |
3 月 2 日有 3 人 → 按名字规则排序 → Tim(3) Bill(4) Avril(5)
4 月 5 日有 3 人 → Candy(5) Sufia(5) Lagrange(8),Candy 和 Sufia 同长度按字典序
输出:
3 2 Tim Bill Avril
4 5 Candy Sufia Lagrange三、参考代码
#include <bits/stdc++.h>
using namespace std;
struct Student {
string name;
int month, day;
};
bool cmpByDate(Student a, Student b) {
if (a.month != b.month)
return a.month < b.month;
return a.day < b.day;
}
bool cmpByName(Student a, Student b) {
if (a.name.length() != b.name.length())
return a.name.length() < b.name.length();
return a.name < b.name;
}
int main() {
int n;
cin >> n;
Student a[185]; // n <= 180
for (int i = 0; i < n; i++) {
cin >> a[i].name >> a[i].month >> a[i].day;
}
sort(a, a + n, cmpByDate); // 按日期排序
bool hasSame = false; // 是否有生日相同的人
int i = 0;
while (i < n) {
int j = i;
// 找到同一天的所有人 [i, j)
while (j < n && a[j].month == a[i].month && a[j].day == a[i].day) {
j++;
}
int cnt = j - i;
if (cnt >= 2) {
hasSame = true;
// 对同一天的人按名字规则排序
sort(a + i, a + j, cmpByName);
cout << a[i].month << " " << a[i].day;
for (int k = i; k < j; k++) {
cout << " " << a[k].name;
}
cout << endl;
}
i = j; // 跳到下一组
}
if (!hasSame) {
cout << "None" << endl;
}
return 0;
}四、复杂度分析
- 时间复杂度:,主要开销在排序。,非常快。
- 空间复杂度:,存储 个学生信息。
五、易错点
- 名字排序规则特殊:先按长度,长度相同再按字典序。不是直接按字典序。
- 输出格式:每行先输出月、日,然后是该天所有学生的名字,空格分隔。
- 无相同生日时输出
None:别漏掉这个特判。 - 日期比较:先比月再比日,不能用
month * 100 + day来简化(虽然本题中可行,但不直观)。
