-https://ac.nowcoder.com/acm/contest/54877/D
- 观察题目,以猫猫的友善值为横坐标,与猫猫期望的友善值为纵坐标,则人类的友善值为纵坐标,期待的友善值为横坐标
- 问题就转换为了求猫猫坐标左上角的最左上的人类坐标点
- 对猫猫以坐标形式排个序,遍历每个猫猫,在遍历过程中维护最左上角的人类坐标点的友善值,并检查答案是否合法,并记录答案
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int n,m;
//离线询问
struct node{
int x,y,id;
};
node cat[200010],peo[200010];
int ans[200010];
bool cmp(node a,node b){
if(a.x!=b.x) return a.x<b.x;
if(a.y!=b.y) return a.y<b.y;
return a.id<b.id;
}
int main(){
cin>>n>>m;
for(int i = 1;i<=n;i++){
cin>>cat[i].x;
cat[i].id = i;
}
for(int i = 1;i<=n;i++){
cin>>cat[i].y;
}
for(int i = 1;i<=m;i++){
cin>>peo[i].y;
peo[i].id = i;
}
for(int i = 1;i<=m;i++){
cin>>peo[i].x;
}
sort(cat+1,cat+1+n,cmp);
sort(peo+1,peo+m+1,cmp);
int p = 1;
int maxl = -1;
for(int i = 1;i<=n;i++){
while(p<=m&&peo[p].x<=cat[i].x){
maxl = max(maxl,peo[p].y) ;
p++;
}
if(maxl >=cat[i].y) ans[cat[i].id] = maxl;
else ans[cat[i].id] = -1;
}
for(int i = 1;i<=n-1;i++){
cout<<ans[i]<<" ";
}
cout<<ans[n];
}