poj 2726 Holiday Hotel (排序）

1. Any hotel which is closer to the seashore than M will be more expensive than M. 
   
2. Any hotel which is cheaper than M will be farther away from the seashore than M.

那么任意比m距离近的旅馆都比m的价格贵的m 一定是candidate hotel 的，

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=10001;
struct edge
{
    int dis,cost;
}map[maxn];
bool cmp(edge x,edge y)//按照距离从小到大排序，距离相等的按照价格排序
{
    if(x.dis == y.dis){
<span style="white-space:pre">		</span>return x.cost < y.cost;
<span style="white-space:pre">	</span>}
<span style="white-space:pre">	</span>return x.dis < y.dis;
}
int main()
{
    int n,i,ans,count;
    while(scanf("%d",&n)&&n)
    {
        ans=maxn;
        count=0;
        for(i=0;i<n;i++)
            scanf("%d%d",&map[i].dis,&map[i].cost);
        sort(map,map+n,cmp);
        for(i=0;i<n;i++)
        {
            if(map[i].cost<ans)
            {
                count++;
                ans=map[i].cost;
            }
        }
        printf("%d\n",count);
    }
    return 0;
}

只要将距离相同的hotel中价格最低的存下来，数组的序号就是距离。
hotel[distance]=min(price);再统计数列中非递增的个数就是结果。

#include <cstdio>
#include <cstring>
const int maxn=10001;
int map[maxn];
int main()
{
    int n,i,dis,cost,len,j,count,min;
    while(scanf("%d",&n)&&n)
    {
        len=0;
        count=1;
        for(i=0;i<maxn;i++)
            map[i]=maxn;
        for(i=0;i<n;i++)
        {
            scanf("%d%d",&dis,&cost);
            if(map[dis]>cost) map[dis]=cost;//保存最低的价格
            if(len<dis) len=dis;
        }
        i=0;
        while(map[i]==maxn) i++;
        min=map[i];
        for(j=i+1;j<=len;j++)
        {
            if(map[j]<min)
            {
                count++;//求非递增的个数
                min=map[j];
            }
        }
        printf("%d\n",count);
    }
    return 0;
}