2408.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"stdio.h"
#include"algorithm"

int n,m;

struct word
{
	char *w;
	int a[30];
}w[30010];

struct group
{
	int begin;
	int end;
	int size;
}g[30010];

int cmp(word a,word b)
{
	for(int i=0;i<26&&a.a[i]==b.a[i];i++)
		;
	return a.a[i]<b.a[i] || i==26&&strcmp(a.w,b.w)<0 ;
}

int cmp1(group a,group b)
{
	if(a.begin<0||a.begin>n||b.begin<0||b.begin>n)
			while(1)printf("faint");
	return a.size>b.size || (a.size==b.size&&strcmp(w[a.begin].w,w[b.begin].w)<0);
}


int main()
{
	int i,j,k;
	char temp[2000];

	for(n=0;scanf("%s",temp)==1;n++)
	{
		w[n].w=new char[strlen(temp)+1];
		w[n].w[strlen(temp)]='\0';
		strcpy(w[n].w,temp);

		for(i=0;i<27;i++)
			w[n].a[i]=0;
		
		for(i=0;w[n].w[i];i++)
			w[n].a[ w[n].w[i]-'a' ]++;
	}
	if(n>30000)
		while(1)printf("faint");
	std::sort(w,w+n,cmp);
	
	for(i=0,j=0;i<n;i++)
	{

		if(!i||std::lexicographical_compare(w[i].a,w[i].a+26,w[i-1].a,w[i-1].a+26)
			 ||std::lexicographical_compare(w[i-1].a,w[i-1].a+26,w[i].a,w[i].a+26) )
		{
			if(j)g[j-1].end=i;

			g[j].begin=i;
			j++;
		}
	}

	g[j-1].end=n;
	
	m=j;
	for(i=0;i<m;i++)
		g[i].size=g[i].end-g[i].begin;

	std::sort(g,g+m,cmp1);

	for(k=0;k<5&&k<m;k++)
	{
		printf("Group of size %d:",g[k].size);
		
		for(i=g[k].begin;i<g[k].end;i++)
		{
			if(i==g[k].begin||strcmp(w[i].w,w[i-1].w)!=0)
				printf(" %s",w[i].w);
		}
	 
		printf(" .\n");
	}
	return 0;
}