rt
代码：
/*
ID:   talenth1
PROG: p2418
LANG: C++
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cmath>
#define maxl 35
using namespace std;
struct Node{
	int num,s;
	char name[maxl];
	Node *left,*right;
	Node();
	};
Node ::Node()
{
	memset(name,0,sizeof(name));
	s=num=0;
	left=right=NULL;
}
int n;
Node *root; 
void LeftRotate(Node * &t)
{
	Node *k=t->left;
	t->right=k->left;
	k->left=t;
	k->s=t->s;
	t->s=t->left->s+t->right->s+1;
	t=k;
}
void RightRotate(Node * &t)
{
	Node *k=t->right;
	t->left=k->right;
	k->right=t;
	k->s=t->s;
	t->s=t->left->s+t->right->s+1;
	t=k;
}
void Maintain(Node *t,bool flag)
{
	if(!flag){
		if(t->left==NULL)return;
		if(t->left->left==NULL)return;
		if(t->left->left->s > t->right->s)
			RightRotate(t);
		else if(t->left->right->s > t->right->s){
			LeftRotate(t->left);
			RightRotate(t);
			}
			else return;
		}
	else {
		if(t->right==NULL)return;
		if(t->right->right==NULL)return;
		if(t->right->right->s > t->left->s)
			LeftRotate(t);
		else if(t->right->left->s > t->left->s){
			RightRotate(t->right);
			LeftRotate(t);
			}
			else return;
		}
	Maintain(t->left,false);
	Maintain(t->right,true);
	Maintain(t,false);
	Maintain(t,true);
}
void ins(char *str)
{
	Node *x=root,*y=NULL;
	while(x!=NULL){
		y=x;
		if(strcmp(str,x->name)==0){
			x->num++;
			return;
			}
		x->s++;
		if(strcmp(str,x->name)<0)
			x=x->left;
		else x=x->right;
		}
	Node *p=new(Node);
	p->s=1;
	p->num=1;
	strcpy(p->name,str);
	if(y==NULL)root=p;
	else if(strcmp(str,y->name)<0){
			y->left=p;
			Maintain(y,false);
			}
		 else {
			y->right=p;
			Maintain(y,true);
			}
}
void destory(Node*t)
{
	if(t->left!=NULL)destory(t->left);
	if(t->right!=NULL)destory(t->right);
	delete(t);
}
void goaround(Node *t)
{
	if(t->left!=NULL)goaround(t->left);
	printf("%s %.4lf\n",t->name,(t->num)*100.0/n);
	if(t->right!=NULL)goaround(t->right);
}
void datain()
{
    char tmp[30];
    n=0;
	while(gets(tmp)!=NULL){
		ins(tmp);
		n++;
		}
}
void work()
{
	goaround(root);
	destory(root);
}
int main()
{ 
    datain();
    work();
    return 0;
}