POJ 1828 选猴王 排序qsort应用

今天总算上完一门课了，以后做OJ的时间可以渐渐多一些。好几天疲于奔命，OJ也没写几题，囧。今天补起来，补一篇处女博!

这题很简单，但是第一次做的时候没有排序采用暴力判断超时，后来想到先排序再判断更快。

#include <iostream>
using namespace std;
struct mon{
	int x;
	int y;
};
//按照x y升序排列，如果不排序直接判断容易超时
int cmp(const void *a,const void *b)  
{  
    mon *p1=(mon *)a;  
    mon *p2=(mon *)b;  
    if(p1->x==p2->x)  
        return p1->y - p2->y;  
    return p1->x - p2->x;  //保证x升序
}  
int main(){
	int n;
	int i,max;
	mon aa[50002];
	int num;
	while(1){
		cin>>n;
		if (n == 0)
			break;	
		for (i = 0;i < n; i++)
			cin>>aa[i].x>>aa[i].y;
		//下面遍历所有的点，对每一个点考察是否是KING
		qsort(aa,n,sizeof(mon),&cmp);
		num = 1;
		max = aa[n-1].y;
		for (i = n-2;i >= 0;i--)
		{
			if (max < aa[i].y)
			{
				max = aa[i].y;
				num++;
			}
		}
		cout<<num<<endl;
	}
	return 0;
}