今天中午收到前天晚上在当当网定的书，当当的送书效率着实让我受惊若宠了一下。说来惭愧，三本书中两本是马上期中考试了的科目，因为觉着科目浮云，就连书都拖着到现在才买。当然，那本觊觎已久的APUE的到来还是让我兴奋了一下。今天早上自学完成OS之后还在愁上课没事干，下午这本圣经就突如其来的到手了。不过那700+页数的厚度还是很恐怖的。慢慢啃吧。啃完它再啃两本《UNIX网络编程》。
言归正传，今天在逛M牛的博客的时候，发现了一个很好的算法题，正在感慨算法的精妙时，突然就在北邮的新oj发现了这么一道题，于是就做了。
题目是说要求在内存1000K的条件下，完成记录一个10^6次方大小的数组的相同元素个数大于1%所有元素，并且按出现次数降序排列（出现次数相等则按元素从小到达排列）。
这题的直观想法是，用一个数组记录每个值出现的次数，但题目中说每个数的范围是2*10^9，因此直接打消了我这个念头。1000K的内存甚至不足以记录所有10^6个数。因为这题明显改编自在M牛那看到的那道题，因此观察输入，将数组输入两遍，这就相当于我们只可以对原数组扫描两遍便得出结果。这里就要引出这个很牛逼的算法。
第一遍扫描，我们用一张100大小的表记录某个元素的出现的次数，当这个表在扫描到某个元素时超过了100个记录时，则对表中的每个元素的出现次数减一，这样就能保证将表的元素数控制在100以下。当处理最后一个数时，无论是否超过100个元素，都将这个值添加到表中。
这个第一遍找出的元素包含但不限于所有满足要求的结果。证明如下：反正，设总共有n个元素，且有一个x的出现次数p>=n/100。若x不在这个集合中，则必有在这个x之后又做了至少p次对所有出现次数减一的操作。因为每次操作减少100个元素，因此有减少了100p，而数组中总共有n个元素，且最后一个元素不会被去掉，因此100p<n，这与p>=n/100矛盾，得证。
有了这样一个集合，我们就在第二遍输入的过程中简单记录在这个集合中的元素出现的次数，并且最后去掉所有不满足要求的元素（出现次数<1%，排序输出即可。因为这个表最大不超过100，因此是O(1)，因此不超过1000K的内存限制。
code:

#include<stdio.h>
#include<stdlib.h>
struct NODE
{
	int num,count;
	NODE *next;
};
int main()
{
	int n,in;
	int total,flag;
	int i,j,k;
	NODE *p,*q,*r;
	NODE head,ans;
	while(scanf("%d",&n)!=EOF)
	{
		head.next=NULL;
		ans.next=NULL;
		total=0;
		for(i=0;i<n;i++)
		{
			scanf("%d",&in);
			p=head.next;
			flag=0;
			while(p)
			{
				if(p->num==in)
				{
					p->count++;
					flag=1;
					break;
				}
				p=p->next;
			}
			if(!flag&&total<100)
			{
				p=new NODE;
				p->num=in;
				p->count=1;
				p->next=head.next;
				head.next=p;
				total++;
			}
			else if(!flag)
			{
				p=new NODE;
				p->num=in;
				p->count=1;
				p->next=head.next;
				head.next=p;
				total++;
				p=head.next;
				q=&head;
				if(i<n-1)
				while(p)
				{
					if((--(p->count))==0)
					{
						q->next=p->next;
						total--;
						delete p;
						p=q->next;
					}
					else
					{
						q=p;
						p=p->next;
					}
				}
			}
		}
		//printf("!n");
		p=head.next;
		while(p)
		{
			p->count=0;
			p=p->next;
		}
		for(i=0;i<n;i++)
		{
			scanf("%d",&in);
			p=head.next;
			while(p)
			{
				if(p->num==in)
				{
					p->count++;
					break;
				}
				p=p->next;
			}
		}
		//printf("aan");
		p=head.next;
		while(p)
		{
			q=ans.next;
			r=&ans;
			flag=0;
			while(q)
			{
				if(p->count>q->count)
				{
					flag=1;
					break;
				}
				else if(p->count==q->count&&p->num<q->num)
				{
					flag=1;
					break;
				}
				r=q;
				q=q->next;
			}
			NODE *temp;
			temp=new NODE;
			temp->num=p->num;
			temp->next=q;
			temp->count=p->count;
			r->next=temp;
			p=p->next;
		}
		p=ans.next;
		q=&ans;
		while(p)
		{
			//printf("p->count:%dn",p->count);
			if(n%100)
			{
				if(p->count<=n/100)
				{
					q->next=p->next;
					delete p;
					p=q->next;
					continue;
				}
			}
			else
			{
				if(p->count<n/100)
				{
					q->next=p->next;
					delete p;
					p=q->next;
					continue;
				}
			}
			q=p;
			p=p->next;
		}
		p=ans.next;
		while(p)
		{
			printf("%d",p->num);
			p=p->next;
			if(p)
			printf(" ");
			else
			printf("n");
		}
		p=head.next;
		while(p)
		{
			q=p;
			p=p->next;
			delete q;
		}
		p=ans.next;
		while(p)
		{
			q=p;
			p=p->next;
			delete q;
		}
	}
}