http://acm.pku.edu.cn/JudgeOnline/problem?id=1828看了discuss,很多同学对题意理解有误(刚开始我也理解错了)
主要是这句:
If a monkey lives at the point (x0, y0), he can be the king only if there is no monkey living at such point (x, y) that x>=x0 and y>=y0
成为猴王的条件是,没有任何的一个猴子的x坐标和y坐标都大于它,而不是说猴王的x和y都要最大.
ok,算法也出来了,简单地说: 先对x快速排序,然后统计y , 时间效率是O（n^lgn）
具体细节要自己体会,这题挺经典的.另外快速排序的方法,虽然我也不是第一次用到了,但是仍然不熟练,到网上查了语法再做的.
#include"stdio.h"
#include"stdlib.h"
typedef struct
{
int x;
int y;
}node[50001];
int cmp(const void *pl, const void *pr){ /**////按照x从小到大排序
node *p1 = (node*)pl;
node *p2 = (node*)pr;
if(p1->x == p2->x)
return p1->y - p2->y;
return p1->x - p2->x;
}
void main(){
int num,i,total,maxy;
while(scanf("%d",&num) && num){
for(i=0;i<num;i++)
scanf("%d%d",&nodes[i].x,&nodes[i].y);
qsort(nodes, num, sizeof(node), &cmp); //按照x从小到大排序
total=1; //最后一个猴子的x最大,所以至少有一个猴王. 往前扫描,如果出现某个猴子的y大于当前最大y,total+1
maxy=nodes[num-1].y;
for(i=num-2;i>=0;i--){
if(maxy<nodes[i].y){
maxy=nodes[i].y;
total++;
}
}
printf("%d\n",total);
}
return;
}
另外,在PKU上编译器效率的问题:
同样的程序,我测试了3次.
include的时候,如果用iostream,在 C++编译器下测试,Memory是476K ,时间280MS
换成 stdio.h + stdlib.h ,在C编译器下Memory是464K ,时间171MS
如果是stdio.h + stdlib.h在C++的编译器下测试呢?Memory是464K ,时间155MS
也就是说
,同样的测试数据,要达到最好的效率,应该用纯C的方式写程序,并选择C++编译器judge程序.
