|
常用链接
留言簿(4)
随笔分类
随笔档案
搜索
最新评论

阅读排行榜
评论排行榜
Powered by: 博客园
模板提供:沪江博客
|
|
|
|
|
发新文章 |
|
|
计算Ted后代的年龄并排序 第一次用结构,居然一次AC了,很爽。。 运用递归查找相应节点的上一代年龄,没有则再向上查
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
using namespace std;

struct descedant
  {
char father[20];
char child[20];
int age; //child的年龄
int differ;
void init();
};

void descedant::init() //初始化
  {
age=0;
differ=0;
}

descedant des[100];

void getAge(descedant& d,int n) //递归计算出年龄
  {
for (int j=0;j<n;j++)
 {
if (strcmp(d.father,des[j].child)==0)
 {
if (des[j].age==0) //未计算则递归算上一代
 {
getAge(des[j],n);
}
d.age=des[j].age-d.differ;
break;
}
}
}

int cmp(const void* a,const void* b) //排序,年龄从大到小,若年龄相同则按字典顺序
  {
descedant* c=(descedant*)a;
descedant* d=(descedant*)b;
if (c->age==d->age)
return strcmp(c->child,d->child);
return d->age-c->age;
}
int main()
  {
int n,num,count=1;
scanf("%d",&n);
while (n--)
 {
scanf("%d",&num);
int k=0;
for (int i=0;i<num;i++)
 {
des[k].init();
scanf("%s %s %d",des[k].father,des[k].child,&des[k].differ);
if (strcmp(des[k].father,"Ted")==0)
 {
des[k].age=100-des[k].differ;
}
k++;
}
for (int i=0;i<num;i++)
 {
if (des[i].age==0)
 {
getAge(des[i],num);
}
}
qsort(des,num,sizeof(descedant),cmp);
printf("DATASET %d\n",count++);
for (int i=0;i<num;i++)
 {
printf("%s %d\n",des[i].child,des[i].age);
}
}
}


|
|