我是象每次找到一个极大的值
然后根据这个值,删除中间肯定不是值
然后一直求到全都删除位置


#include <stdio.h>
#include <stdlib.h>

struct monkey
{
	long x;
	long y;
};
struct node
{
	struct monkey pos;
	struct node * pnext;
};
int main()
{
	int n,i;
	while(scanf("%d",&n),n!=0)
	{
		struct monkey temp;
		struct node *phead,*ptemp,*ptail;
		phead=(struct node*)malloc(sizeof(struct node));
		phead->pnext=NULL;
		for(i=0;i<n;++i)
		{
			ptemp=(struct node*)malloc(sizeof(struct node));
			ptemp->pnext=NULL;
			scanf("%d %d",&ptemp->pos.x,&ptemp->pos.y);
			if(i==0)
			{
				temp.x=ptemp->pos.x;
				temp.y=ptemp->pos.y;

				phead=ptemp;
				ptail=ptemp;
			}
			else
			{
				if(temp.x < ptemp->pos.x || temp.x==ptemp->pos.x&&temp.y < ptemp->pos.y)
				{
					temp.x=ptemp->pos.x;
					temp.y=ptemp->pos.y;
				}
				ptail->pnext=ptemp;
				ptail=ptemp;
			}
		}
		int count=0;
		do
		{
			++count;
			for(ptemp=phead,ptail=phead;ptemp!=NULL;)
			{
				
				if(ptemp->pos.x<=temp.x && ptemp->pos.y<=temp.y)
				{
					if(ptemp==phead)
					{
						phead=phead->pnext;
						ptemp=phead;
						ptail=phead;
					}
					else
					{
						ptail->pnext=ptemp->pnext;
						ptemp=ptail->pnext;
					}
				}
				else 
				{
					ptail=ptemp;
					ptemp=ptemp->pnext;
				}
			}	
			for(ptemp=phead;ptemp!=NULL;ptemp=ptemp->pnext)
			{
				if(ptemp==phead||temp.x>ptemp->pos.x || temp.x==ptemp->pos.x&&temp.y > ptemp->pos.y)
				{
					temp.x=ptemp->pos.x;
					temp.y=ptemp->pos.y;
				}
			}
		}while(phead!=NULL);
		printf("%d\n",count);
	}
	return 0;
}


			
	

• Re:这个题好象没有人问~不好意思,能不能给个提示! (1867) atlas_of_rruucc 2004-09-12 22:56:23
  • 他妈的测试数据太弱了,O(n^2)居然都可以过！！！ (75) saturnalia 2005-08-13 16:52:04
  • 这个所谓的提示是错的 (75) saturnalia 2005-08-13 16:53:26
    • 您怎么知道是错的呢? (0) c0500448242 2005-08-13 17:47:03
      • Re:您怎么知道是错的呢? (138) wzhh 2006-08-29 11:10:24
        • 您是怎么算的啊~~~难道按那个提示算出来不是3吗 Re:您怎么知道是错的呢? (158) ttmmpp 2006-08-29 13:48:41
• 呵呵，O(nlogn)的算法还是不难实现的 (2) gz2001 2004-09-13 07:45:38
  • O(n^2)就可以过了 (4) T5 2004-09-13 10:27:24
• 想法太复杂，用筛法就可以AC了，时间O（n^2）。 (107) huicpc39 2005-09-08 21:24:22