http://acm.pku.edu.cn/JudgeOnline/problem?id=1828看了discuss,很多同學(xué)對(duì)題意理解有誤(剛開始我也理解錯(cuò)了)
主要是這句:
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
成為猴王的條件是,沒(méi)有任何的一個(gè)猴子的x坐標(biāo)和y坐標(biāo)都大于它,而不是說(shuō)猴王的x和y都要最大.
ok,算法也出來(lái)了,簡(jiǎn)單地說(shuō): 先對(duì)x快速排序,然后統(tǒng)計(jì)y , 時(shí)間效率是O（n^lgn）
具體細(xì)節(jié)要自己體會(huì),這題挺經(jīng)典的.另外快速排序的方法,雖然我也不是第一次用到了,但是仍然不熟練,到網(wǎng)上查了語(yǔ)法再做的.
#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; //最后一個(gè)猴子的x最大,所以至少有一個(gè)猴王. 往前掃描,如果出現(xiàn)某個(gè)猴子的y大于當(dāng)前最大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上編譯器效率的問(wèn)題:
同樣的程序,我測(cè)試了3次.
include的時(shí)候,如果用iostream,在 C++編譯器下測(cè)試,Memory是476K ,時(shí)間280MS
換成 stdio.h + stdlib.h ,在C編譯器下Memory是464K ,時(shí)間171MS
如果是stdio.h + stdlib.h在C++的編譯器下測(cè)試呢?Memory是464K ,時(shí)間155MS
也就是說(shuō)
,同樣的測(cè)試數(shù)據(jù),要達(dá)到最好的效率,應(yīng)該用純C的方式寫程序,并選擇C++編譯器judge程序.
