题目链接：https://cn.vjudge.net/problem/Gym-100971D
题目大意：给你n个城市的信息，每一个城市的信息包括坐标和人数，然后让你找每一个城市的父亲，作为一个城市的父亲具体满足的条件是：作为父亲的城市的坐标和当前城市的人数最多，，如果有多个满足的城市，则和原来的点相隔最近的作为父亲。
具体思路：首先，题目中说坐标和人数是不会有相同的值，所以我们对于每一个点，按照x轴进行排序之后，找出当前点的左边的第一个人数大于当前点的，然后再找出当前点的右边的第一个人数大于当前点的，这个过程可以通过单调栈来维护，然后再具体找的过程中，先看当前的这个点的左边和右边时候都存在，如果都没有，就证明没有父亲，如果有一个，这个点就是父亲，如果都有的话，就是寻找相隔最近的就可以了。
AC代码：
#include<iostream>
#include<stack>
#include<cmath>
#include<stdio.h>
#include<algorithm>
#include<stack>
#include<string>
using namespace std;
# define ll long long
const int maxn = 2e5+;
int L[maxn],R[maxn];
int val[maxn],x[maxn];
int pos[maxn],ans[maxn];
bool cmp(int t1,int t2){
return x[t1]<x[t2];
}
int main(){
int n;
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%d %d",&x[i],&val[i]);
pos[i]=i;
}
sort(pos+,pos+n+,cmp);
stack<int>q;
for(int i=;i<=n;i++){
if(!q.empty())L[pos[i]]=-;
while(!q.empty()&&val[q.top()]<=val[pos[i]])q.pop();
if(q.empty())L[pos[i]]=-;
else L[pos[i]]=q.top();
q.push(pos[i]);
}
while(!q.empty())q.pop();
for(int i=n;i>=;i--){
if(!q.empty())R[pos[i]]=-;
while(!q.empty()&&val[q.top()]<=val[pos[i]])q.pop();
if(q.empty())R[pos[i]]=-;
else R[pos[i]]=q.top();
q.push(pos[i]);
}
for(int i=;i<=n;i++){
if(L[i]==-&&R[i]==-)ans[i]=-;
else if(L[i]==-)ans[i]=R[i];
else if(R[i]==-)ans[i]=L[i];
else {
if(abs(x[R[i]]-x[i])>abs(x[L[i]]-x[i]))ans[i]=L[i];
else if(abs(x[R[i]]-x[i])<abs(x[L[i]]-x[i]))ans[i]=R[i];
else {
if(val[R[i]]>val[L[i]])ans[i]=R[i];
else ans[i]=L[i];
}
}
}
for(int i=;i<=n;i++){
if(i==)printf("%d",ans[i]);
else printf(" %d",ans[i]);
}
printf("\n");
return ;
}