#include <stdio.h>
#include <algorithm>
char a[50000][8];
typedef unsigned short sh;
struct menber
{
	sh p,n,m;
}b[50000];
sh r[50000],t[50000];
bool cmp(const sh &x,const sh &y)
{
	return r[x]>r[y];
}
void inline run(sh x,sh y,sh l)
{
	sh i;
	b[x].p++; b[y].n++;
	if(x==y) return;
	for(i=l;;i++) {if(t[i]>=x&&t[i]<=y) break;}
	if(t[i]!=x) run(x,t[i]-1,i+1);	
	if(t[i]!=y) run(t[i]+1,y,i+1);
}
int main()
{
	sh n,i,j;
	char c;
	while(scanf("%d",&n)&&n)
	{
		for(i=0;i<n;i++)
		{
			getchar();
			j=0;
			c=getchar();
			while(c!='/') {a[i][j++]=c; c=getchar();}
			a[i][j++]='/'; a[i][j]='\0';
			b[i].p=0; b[i].n=0;
			scanf("%d",&b[i].m);
			r[i]=b[i].m; t[i]=i;
		}
		std::sort(t,t+n,cmp);
		run(0,n-1,0);
		for(i=0;i<n;i++)
		{
			while(b[i].p--) putchar('(');
			printf("%s%d",a[i],b[i].m);
			while(b[i].n--) putchar(')');
		}
		putchar('\n');
	}
	return 0;
}

• 要先按字符串排序的..然后再建笛卡儿树 (0) liangzhirong 2007-03-09 11:32:36
  • Re:要先按字符串排序的..然后再建笛卡儿树 (0) tank_Cs 2007-03-31 10:01:39