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