ACM PKU 2726 Holiday Hotel

和PKU1828原理相同;唯一不同的是1828要求的是x>=maxx||y>=maxy ，这道题却相反.
时间复杂度仍然是O(NlogN)

#include"stdio.h"
#include"stdlib.h"

 
 typedef struct{
    int D;
     int C;
 }node;
 node nodes[10001];
 

 
int cmp(const void *pl, const void *pr){   //按照D从小到大排序
    node *p1 = (node*)pl; 
     node *p2 = (node*)pr;
     if(p1->D == p2->D)           
         return p1->C - p2->C;
    return p1->D - p2->D;
 }
 
 int main(){
     int num,i;
     while(scanf("%d",&num) && num){
         for(int i=0;i<num;i++)
             scanf("%d%d",&nodes[i].D,&nodes[i].C);
         qsort(nodes, num, sizeof(node), &cmp); //按照D从小到大排序

       int total=1;                 
         int min=nodes[0].C;
        for(i=1;i<=num-1;i++){
             if(min>nodes[i].C){
                min=nodes[i].C;
                 total++;
             }
         }
         printf("%d\n",total);
     }
     return 0;
 }

posted on 2007-09-21 01:35 流牛ζ木马 阅读(946) 评论(0)  编辑 收藏 引用


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


<2007年9月>
日一二三四五六
2627282930311
2345678
9101112131415
16171819202122
23242526272829
30123456

导航

统计

公告

MY Email/MSN :mars1021@163.com QQ : 27402040 流牛ζ木马

常用链接

留言簿(6)

随笔档案

相册

搜索

最新随笔

最新评论

阅读排行榜

评论排行榜