2397826_ac_0ms_524k.cc

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
#define INIT (Tree *)malloc(sizeof(Tree))
int no;
struct node
{
	char p_name[100];
	int num;
}pj[1000];

typedef struct Node
{
	char name[100];
	int id;
	struct Node *l, *r;
}Tree;

Tree *head, *s, *p;

bool cmp(struct node a,struct node b)
{
	if(a.num!=b.num)
		return a.num>b.num;
	else
		return strcmp(a.p_name,b.p_name)<0;
}

int main()
{
	int mark;
	char tmp[100];

	while(1)
	{
		mark = 1;no = 0;
		gets(tmp);
		pj[0].num = 0;
		strcpy(pj[0].p_name,tmp);
		if(tmp[0]=='0')
			break;
		while(gets(tmp))
		{
			if(tmp[0]=='1')
				break;
			if(tmp[0]<='Z')
			{
				no++;
				strcpy(pj[no].p_name,tmp);
				pj[no].num = 0;
				continue;
			}
			pj[no].num++;
			s = head;
			if(mark)
			{
				head = INIT;
				mark = 0;
				strcpy(head->name,tmp);
				head->l = head->r = NULL;
			}
			else
			{
				while(s)
				{
				if(strcmp(s->name,tmp)>0)
					if(s->l)
						s = s->l;
					else
					{
						p = INIT;
						strcpy(p->name,tmp);
						p->id = no;
						p->l = p->r = NULL;
						s->l = p;
						break;
					}
					else
						if(strcmp(s->name,tmp)<0)
						{
							if(s->r)
								s = s->r;
							else
							{
								p = INIT;
								strcpy(p->name,tmp);
								p->id = no;
								p->l = p->r = NULL;
								s->r = p;
								break;
							}
						}
						else
						{
							if(s->id!=no)
								pj[s->id].num--,s->id = -1;
							pj[no].num--;
							break;
						}
				}
			}	
		}
		sort(pj,pj+no+1,cmp);
		for(int i = 0; i <= no; i++)
			printf("%s %d\n",pj[i].p_name,pj[i].num);
	}
	return 1;
}