题目分析

我们需要根据给定的出生证明信息，构建 Ted 的后代家族树，并计算每个后代的年龄。最终需要按年龄从大到小排序，年龄相同的按名字字典序排列。

关键点：

1. 年龄计算：Ted 的年龄固定为 $100$ 岁，其他后代的年龄需要通过出生证明中的父亲年龄递推得到。
2. 家族关系：所有后代都是 Ted 的直接或间接孩子，且出生证明完整（无缺失）。
3. 排序规则：年龄降序，同年龄按名字字典序升序。

解题思路

1. 数据结构选择：

   • 使用一个字典（或哈希表）age_map 记录每个人的年龄，初始时只有 Ted，年龄为 $100$。
   • 用一个列表存储所有出生证明信息。

2. 年龄计算：

   • 对于每个出生证明 FNAME CNAME FAGE，孩子的年龄为 age_map[FNAME] - FAGE。
   • 需要确保在处理孩子之前，其父亲的年龄已经被计算（可能需要多次遍历）。

3. 处理顺序：

   • 由于家族关系可能存在多代依赖（如祖父→父亲→孩子），需要按照拓扑顺序处理，确保父亲先于孩子被处理。
   • 可以通过多次遍历出生证明列表来实现，直到所有后代的年龄都被计算。

4. 排序输出：

   • 收集所有后代的姓名和年龄，按题目要求排序。

解决代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <string>
using namespace std;

const int maxn=100+5;

struct people{
	int age,year;
	string fname,name;
}x[maxn];

bool cmp(people a,people b){
	
	if(a.age==b.age)
		return a.name<b.name;
	return a.age>b.age;
}
int main(){
	
	int t;
	cin>>t;
	for(int j=1;j<=t;j++){
		int n;
		cin>>n;
		for(int i=0;i<n;i++){
			x[i].age=0;
			cin>>x[i].fname>>x[i].name>>x[i].year;
			if(x[i].fname=="Ted")
				x[i].age=100-x[i].year;
		}
		
		for(int i=0;i<n;i++){
			string fs=x[i].fname;
			for(int j=0;j<n;j++){
				if(x[j].name==fs && x[j].age!=0){
					x[i].age=x[j].age-x[i].year;
					break;
				}
			}
		}
		sort(x,x+n,cmp);
		cout<<"DATASET "<<j<<endl;
		for(int i=0;i<n;i++)
			cout<<x[i].name<<" "<<x[i].age<<endl;
	}
	return 0;
}

代码解释

1. 输入处理：

   • 使用 sys.stdin.read 快速读取所有输入，按行分割。
   • 第一个数字是数据集数量 $n$，随后逐个处理每个数据集。

2. 年龄计算：

   • 初始化 age_map，设置 Ted 的年龄为 $100$。
   • 通过多次遍历出生证明列表，确保所有后代的年龄被正确计算（父亲年龄已知时才计算孩子年龄）。

3. 排序输出：

   • 收集所有后代的姓名和年龄到列表 descendants。
   • 使用 sort 方法，按年龄降序、名字升序排序。
   • 按格式输出结果。

这种方法确保正确处理家族关系的依赖顺序，并通过多次遍历保证所有年龄被正确计算，最终按要求排序输出。