这样是比较慢
可以考虑先把点按Y值从大到小排序
然后从大到小扫描一边
扫描时如果该点X值大于之前X的最大值答案就加1

> 我是象每次找到一个极大的值
> 然后根据这个值,删除中间肯定不是值
> 然后一直求到全都删除位置
> 
> 
> #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;
> }
> 
> 
> 			
> 	

• 他妈的测试数据太弱了,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