[POJ][2726][单调栈] Holiday Hotel

题目大意：

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

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

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

思路：

单调栈模板题。

代码：

#include
#include
#include
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 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());
        //栈中剩下的酒店都是候选酒店。 
    }
}