#include<stdio.h>
struct stat
{
	char s[10];
	long int num;
};
char a1[1000001][20];
char b1[1000001][10];
long int num1[1000001];
struct stat st1[1000001];
int exchange(struct stat *a,struct stat *b)   //交互
{
	struct stat c;
	c=*a;
	*a=*b;
	*b=c;
	return 0;
}
int mini(char *a,char *b)     //比较字符串大小的子函数
{
	long int i;
	long int j;
	for(i=0;i<=7;i++)
	{
		if(a[i]<b[i])
		{
			j=1;
			break;
		}
		else if(a[i]>b[i])
		{
			j=0;
			break;
		}
	}
	return j;
}
int sort(struct stat *a,struct stat *b,struct stat *c) //借助交换操作，进行三者排大小，k是用来区分情况的标志
{
	int k=0;
	if(mini(a->s,b->s)==0)
	{
		if(mini(b->s,c->s)==0)
		{
			exchange(a,c);
			k=3;
		}
		else
		{
			exchange(a,b);
			k=2;
		}
	}
	else if(mini(a->s,c->s)==0)
	{
		exchange(a,c);
		k=3;
	}
	else k=1;
	return k;
}	
int change(char *a,char *b)          //使字符串规范化XXX-XXXX
{
	long int i,j=0;
	for(i=0;i<=15;i++)              
	{
		if(a[i]=='\0')
			break;
		else if(a[i]<=57&&a[i]>=48)
		{
			if(j==3)
			{
				b[j]='-';
				i--;
			}
			else
				b[j]=a[i];
			j++;
		}
		else if(a[i]<=89&&a[i]>=65)
		{
			if(j==3)
			{
				b[j]='-';
				i--;
			}
			else
			{
				if(a[i]>80)
				a[i]=a[i]-1;
				b[j]=(a[i]-65)/3+50;
			}
			j++;
		}
		
	}
	return 0;
}
int judge(char *a,char *b)             //判断两个字符串是否相同
{
	long int i,j=0;
	for(i=0;i<=7;i++)
	{
		if(a[i]!=b[i])
		break;
	}
	if(i==8)
		return 1;
	else 
		return 0;
}
int sort_s(struct stat *st,int n)   //字符串排序
{
	long int i=1;
	int k=5;
	long int j;
	while(n>1)
	{
		for(i=n/2;i>=1;i--)
		{
			j=i;
			k=5;
			if((2*j+1)<=n)
			{
				while(k!=1&&(2*j<=n))
				{
					if(2*j+1<=n)
					{
						k=sort(&st[j],&st[2*j],&st[2*j+1]);
						j=(k/2+1)*j+k%2;
					}
					else
					{
						if(mini(st[j].s,st[2*j].s)==0)
						{
							exchange(&st[j],&st[2*j]);
							j=2*j;
						}
						k=1;
					}
				}
			}
			else
			{
				if(mini(st[j].s,st[2*j].s)==0)
				{
					exchange(&st[j],&st[2*j]);
					j=2*j;
				}
			}
		}
	printf("%s",st[1].s);
	printf(" %d\n",st[1].num);
		exchange(&st[1],&st[n]);
		n--;
	}
	printf("%s",st[1].s);
	printf(" %d\n",st[1].num);
	return 0;
}
int main()
{
	long int i=1,quan=0,k=0,j=1;         //i,j,k通用的变量，quan是控制输入号码个数的
	scanf("%d",&quan);
	while(j<=quan)                     //输入
	{
		scanf("%s",a1[j]);
		j++;
	}
	j=1;
	while(j<=quan)                      //规范化字符串
	{
		change(a1[j],b1[i]);
		for(k=1;k<i;k++)
		{
			if(judge(b1[k],b1[i])==1)
			{
				num1[k]++;
				break;
			}
		}
		if(k==i)
			{
			    num1[i]=1;
				i++;	
			}
		j++;
	}
	k=1;
	for(i=1;num1[i]!=0;i++)          //装配结构体，同时去除没有重复的号码
	{
		if(num1[i]!=1)
		{
			for(j=0;j<=7;j++)
			st1[k].s[j]=b1[i][j];
			st1[k].num=num1[i];
			k++;
		}
	}
	k--;                              //有重复的号码个数
	if(k==0)
		printf("No duplicates.\n");
	else
		sort_s(st1,k);                   //调用字符串排序子程序
	return 0;
}

• Re:各位，我是新手，请指教：用的堆排，为什么总是超时……该怎么改，难道非用快排不可么 (43) lhyan792 2010-04-02 12:37:39
  • 回答 (7) 9777 2010-04-03 10:56:44
    • Re:回答 (34) lhyan792 2010-04-03 14:07:56
• 请用字典树 (3425) yygy 2010-04-02 13:46:26
  • 汗.话说本小菜还是前几周才学会字典树的.. (0) lijinwu 2010-04-02 13:50:55
• Re:各位，我是新手，请指教：用的堆排，为什么总是超时……该怎么改，难道非用快排不可么 (1168) zwjowen 2010-04-12 16:02:38