bon

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  46 Posts :: 0 Stories :: 12 Comments :: 0 Trackbacks

常用链接

留言簿(2)

我参与的团队

搜索

  •  

最新评论

阅读排行榜

评论排行榜

poj两个相似的题目,很有代表性。
pku 1828
pku 2726

题目大意是给出平面上的若干点,找出符合某种要求的点(x0, y0),如要求不存在点(x, y),使得x>=x0 且 y>=y0,换一种说法就是对任意点(x, y)都有x<x0 或 y<y0.
下面给出pku 1828的代码
#include <stdlib.h>
#include 
<stdio.h>

struct node{
    
int x,y;
}
a[50001];

int cmp(const void *aa, const void *bb)
{
    node
* a=(node*)aa;
    node
* b=(node*)bb;
    
if(a->x==b->x) return a->y-b->y;
    
return a->x-b->x;
}


int i,j,k,n;

int main()
{
    
while(scanf("%d",&n) && n!=0)
    
{
        
for(i=0;i<n;i++) scanf("%d%d",&a[i].x, &a[i].y);
        qsort(a,n,
sizeof(node),cmp);
        
//for(i=0;i<n;i++) printf("%d %d\n",a[i].x,a[i].y);
        int total=1;
        
int maxi=a[n-1].y;
        
for(i=n-2;i>=0;i--)
        
{
            
if(a[i].y>maxi)
            
{
                maxi
=a[i].y;
                total
++;
            }

        }

        printf(
"%d\n",total);
    }

    
return 1;
}
posted on 2007-12-30 23:35 bon 阅读(340) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


Google PageRank 
Checker - Page Rank Calculator