本题的大意是：给出一些旅馆的价格和距离，找出满足条件的旅馆，条件是：其他所有旅馆的价格和距离都不同时小于这家旅馆。意思就是也许有的旅馆的价格或距离小于这家旅馆，但不会有一家旅馆的价格和距离同时小于这家旅馆。
本题容易想到的一种方法就是二重循环，对每家旅馆都遍历其他所有旅馆，如果没有一家旅馆的价格和距离同时小于这家旅馆，那就输出。但是这种方法肯定会超时。那么我们就从旅馆的这两个属性下手，先固定其中一个属性，然后比较另一个属性。本题的做法就是：
将所有旅馆的价格作为下标，定义三个数组f[i]，p[i]，d[i]，f[i]=d表示价格为i的所有旅馆中，最小的距离为d；p数组和d数组保存每家旅馆的价格和距离。然后遍历每个旅馆，在价格小于当前遍历到的旅馆的所有旅馆中查询有没有距离也小于此旅馆的，若有则说明有一家旅馆的价格和距离都小于遍历到的这家旅馆了。所以问题就转化成了：对于编号为 i 的旅馆，查询f[0]到f[p[i]]中的最小值，若这个最小值小于d[i]，则这个旅馆不是我们要的旅馆。最后一个要解决的问题就是查询区间的最小值，这里我们使用RMQ问题中的ST算法（详解：ST算法），详见注释。代码如下：
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=10000+5;
const int INF=10000000;
int p[maxn],d[maxn],f[maxn],dp[maxn][15];
//此结构体用来保存结果
struct res
{int price,dis;res(int a,int b){price=a;dis=b;}
};
vector<res> r;
bool cmp(res a,res b)
{if(a.price==b.price)return a.dis<b.dis;elsereturn a.price<b.price;
}void init(int n)
{//因为p[i]是非负的，可能为0，所以f数组的下标从0开始，那么这个dp数组就也应该从0开始初始化 for(int i=0;i<=n;i++)dp[i][0]=f[i];for(int j=1;(1<<j)<=n;j++)for(int i=0;i+(1<<j)<=n+1;i++)dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
}int query(int l,int r)
{if(l>r)return INF;int k=(int)(log((double)(r-l+1))/log(2.0));return min(dp[l][k],dp[r-(1<<k)+1][k]);
}int main()
{int n;while(scanf("%d",&n)!=EOF){//再处理一组数据前先将结果集清空，并初始化f数组 r.clear();for(int i=0;i<=maxn;i++)f[i]=INF;//maxp用来求所有旅馆中的最大价格。f数组的下标的含义是旅馆的价格，所以这个变量就是f数组的长度 int maxp=-1;for(int i=1;i<=n;i++){scanf("%d%d",&p[i],&d[i]);//找出价格为p[i]的所有旅馆的最小距离，并保存最大价格 f[p[i]]=min(f[p[i]],d[i]);maxp=max(maxp,p[i]);}//按最大价格来做为数组的长度 init(maxp);for(int i=1;i<=n;i++){ if(query(0,p[i]-1)<d[i])continue;r.push_back(res(p[i],d[i]));}sort(r.begin(),r.end(),cmp);printf("%d\n",r.size());for(int i=0;i<r.size();i++)printf("%d %d\n",r[i].price,r[i].dis);}return 0;
}