题意分析

给定 $N$ 家酒店，每家酒店都有两个属性：距离 $D$ 和价格 $C$。我们要找出符合“在任一维度上不会被其他酒店同时占优”的候选酒店，也就是找到所有在“距离-价格”平面上位于“Pareto 前沿”的点。

解题思路

1. 先按距离排序并筛选：按 $D$ 从小到大对酒店排序，扫描时维护到当前为止遇到的最小价格 $\min C$。当处理到新的酒店时，如果它的价格小于之前最小价格，说明在所有距离不大于它的酒店中，它是价格最优的；同时当距离相同时，只需对第一个出现的酒店进行判断。标记满足此条件的酒店。

2. 再按价格排序并筛选：按 $C$ 从小到大对酒店排序，扫描时维护到当前为止遇到的最小距离 $\min D$。当处理到新的酒店时，如果它的距离小于之前最小距离，说明在所有价格不高于它的酒店中，它是距离最优的。标记满足此条件的酒店。

3. 最后统计交集：在两次筛选中均被标记的酒店即为满足题意的候选酒店，其总数即为答案。

本题代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
int a[10008];
int b[10008]; 
struct nod{
	int D;//距离 
	int C;//价格 
	int id;
};
int cmp1(nod x,nod y)
{
		return x.D<y.D;
	
}
int cmp2(nod x,nod y)
{
		return x.C<y.C;
}
int main()
{
	while(1)
	{
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		vector<nod> ve;
		int n;
		cin>>n;
		if(n==0)
		{
			break;
		}
		for(int i=0;i<n;i++)
		{
			nod t;
			cin>>t.D>>t.C;
			t.id=i;
			ve.push_back(t);
		}
		sort(ve.begin(),ve.end(),cmp1);
		int qzx=ve[0].C;//钱最小 
		int bjz=ve[0].C;//比较值 
		a[ve[0].id]=1;
		for(int i=1;i<ve.size();i++)
		{
			if(ve[i-1].D<ve[i].D)
			{
				bjz=qzx;
			}
			if(bjz>ve[i].C)
			{
				a[ve[i].id]=1;
			}
			if(qzx>ve[i].C)
			{
				qzx=ve[i].C;
			} 
		}
		sort(ve.begin(),ve.end(),cmp2);
		int jzx=ve[0].D;//距离最小 
		bjz=ve[0].D;
		b[ve[0].id]=1;
		for(int i=1;i<ve.size();i++)
		{
			if(ve[i-1].C<ve[i].C)
			{
				bjz=jzx;
			}
			if(bjz>ve[i].D)
			{
				b[ve[i].id]=1;
			}
			if(jzx>ve[i].D)
			{
				jzx=ve[i].D;
			}
		} 
		int jg=0;
		for(int i=0;i<n;i++)
		{
			if(a[i]==1 && b[i]==1)
			{
				jg++;
			}
		}
		cout<<jg<<endl;
	}
}