UVA 11100 The Trip, 2007

/*
WA

题意：一伙人要去旅游，旅行商分配给他们n个包。但不让带太多的包上飞机，所以他们一个包嵌套一个这样来使外面总包数尽量小。输出外面最小包的个数和嵌套的序列。输入为n的值，和这n个包的体积。

贪心策略：从体积最大的包a开始，把体积比它小的包中最大的哪一个b放入a中，这样再对b进行同样的操作，知道所有的包都被访问。
结果WA，网上的解法，首先求出最少可分成的堆数K，然后依次输出各个序列。见方法二
*/

//方法一：WA，不知道为什么出错？
#include <cstdio>
#include <cstring>
#include <cstdlib>
const int nMax=10007;
int A[nMax];
int nest[nMax];
int visit[nMax];
int n;
int ans;
int cmp(const void *a,const void *b)
{
	int *pa=(int *)a;
	int *pb=(int *)b;
	return *pa-*pb;
}
void search(int cur)
{
	for(int i=cur-1;i>=0;i--)
	{
		if(!visit[i] && A[i]<A[cur])
		{
			nest[i]=cur;
			visit[i]=1;
			search(i);
			break;
		}
	}
}
void solve()
{
	memset(visit,0,sizeof(visit));
	memset(nest,-1,sizeof(nest));
	ans=0;
	for(int i=n-1;i>=0;i--)
		if(!visit[i])
		{
			ans++;
			visit[i]=1;
			search(i);
		}
}
void print()
{
	memset(visit,0,sizeof(visit));
	printf("%d\n",ans);
	for(int i=0;i<n;i++)
	{
		if(!visit[i])
		{
			int p=i;
			while(p!=-1)
			{
				if(p!=i) printf(" ");
				visit[p]=1;
				printf("%d",A[p]);
				p=nest[p];
			}
			printf("\n");
		}
	}
}
int main()
{
	//freopen("f://data.in","r",stdin);
	int first=1;
	while(scanf("%d",&n) && n)
	{
		if(first) first=0;
		else printf("\n");
		for(int i=0;i<n;i++)
			scanf("%d",&A[i]);
		qsort(A,n,sizeof(A[0]),cmp);
		solve();
		print();
	}
	return 0;
}

//方法二：AC

#include <cstdio>
#include <cstdlib>
#include <cstring>
const int nMax=10007;
int n;
int A[nMax];
int num[nMax],r[nMax];
int M;//整合后数组的个数
int next[nMax],first[nMax];//将数组分成K组
int K;
int cmp(const void *a,const void *b)
{
	int *pa = (int *)a;
	int *pb = (int *)b;
	return *pa - *pb;
}
void init()
{
	for(int i=0;i<n;i++)
		scanf("%d",&A[i]);
	qsort(A,n,sizeof(A[0]),cmp);
	int m=0;
	r[0]=-1;
	for(int i=0;i<n;i++)
	{
		if(A[i]==r[m])
			++ num[m];
		else
		{
			++ m;
			num[m] = 1;
			r[m] = A[i];
		}
	}
	M=m;
}
void solve()
{
	K=0;
	for(int i=1;i<=M;i++)
		if(num[i]>K)
			K = num[i];
	memset(first,-1,sizeof(first));
	int e=0;
	for(int i = 0; i < n; ++ i)
	{
		next[i]=first[e];
		first[e]=i;
		e=(e + 1) % K;
	}
}
void print()
{
	printf("%d\n",K);
	for(int i=0;i<K;i++)
	{
		int p = first[i];
		printf("%d",A[p]);
		p=next[p];
		while(p != -1)
		{
			printf(" %d",A[p]);
			p=next[p];
		}
		printf("\n");
	}
}
int main()
{
	//freopen("f://data.in","r",stdin);
	int first=1;
	while(scanf("%d",&n) && n)
	{
		if(first) first=0;
		else printf("\n");
		init();
		solve();
		print();
	}
	return 0;
}