卢俊达

题目大意：

给出一些酒店的价格和其到海岸的距离，要求挑选出一些候选酒店。一个候选酒店要满足以下两个要求:

比酒店M更靠近海岸的酒店的价格都比酒店M贵。

比酒店M更便宜的酒店到海岸的距离都比酒店M到海岸的距离远。

思路：

单调栈模板题。

代码：

#include<iostream>
#include<stdio.h>
#include<stack>
using namespace std;
struct point
//将酒店信息封装在结构体中。 
{
	int dis;
	int cost;
}hotel[10001];
int cmp(const void* m,const void* n)
//将酒店按到海岸距离由远及近，价格由高到底排序。 
{
	if((*(point*)n).dis==(*(point*)m).dis)
		return (*(point*)n).cost-(*(point*)m).cost;
	return (*(point*)n).dis-(*(point*)m).dis;
}
int main()
{
	int n;
	while(scanf("%d",&n)&&n)
	{
		stack<point> s;
		for(int i=0;i<n;i++)
			scanf("%d%d",&hotel[i].dis,&hotel[i].cost);
		qsort(hotel,n,sizeof(hotel[0]),cmp);
		s.push(hotel[0]);
		for(int i=1;i<n;i++)
		{
			while(s.size()&&hotel[i].cost<=s.top().cost)
			//在栈不为空的情况下，判断当前酒店价格是否小于等于栈顶酒店价格。
				s.pop();
				//将栈顶酒店出栈，直到当前酒店价格大于栈顶酒店价格为止。
				//出栈的酒店是不符合候选要求的酒店。 
			s.push(hotel[i]);
		}
		printf("%d\n",s.size());
		//栈中剩下的酒店都是候选酒店。 
	}
}