有n个房间,rooms[i]={id[i],size[i]}
表示第i个房间编号为id[i],面积为size[i],房间编号唯一。
现有k个查询query[j]={preferred[j],minsize[j]}
,表示要求面积至少为minsize[j],且编号跟preferred[j]最接近,如果有多个,选编号小的那个。
1<=n<=1e5; 1<=k<=1e4; 1<=id[i],preferred[i]<=1e7; 1<=size[i],minsize[i]<=1e7
像这种二维偏序查询问题,一般做法是离线处理,对查询按第一维排序,按顺序加入集合,然后在集合中查询第二维信息,这样把二维降成一维来处理。
对于本题,将查询按面积从大到小排序,每次查询前将满足面积条件的房间加入集合,然后在该集合中寻找编号最接近的元素。
struct node {
int idx, id, siz, ans;
};
class Solution {
public:
vector<int> closestRoom(vector<vector<int>>& rooms, vector<vector<int>>& queries) {
int n = rooms.size();
int q = queries.size();
sort(rooms.begin(), rooms.end(), [&](auto &x, auto &y){return x[1]>y[1];});
vector<node> vn(q);
for (int i = 0; i < q; i++) {
vn[i] = {i, queries[i][0], queries[i][1], 0};
}
sort(vn.begin(), vn.end(), [&](auto &x, auto &y){return x.siz > y.siz;});
vector<int> ans(q);
set<int> st;
for (int i = 0, j = 0; i < q; i++) {
while (j < n && rooms[j][1] >= vn[i].siz) {
st.insert(rooms[j][0]);
j += 1;
}
int best = -1, diff = INT_MAX;
auto it = st.lower_bound(vn[i].id);
if (it != st.end() && abs(*it - vn[i].id) < diff) {
diff = abs(*it - vn[i].id);
best = *it;
}
if (it != st.begin()) {
--it;
if (abs(*it - vn[i].id) <= diff) {
diff = abs(*it - vn[i].id);
best = *it;
}
}
ans[vn[i].idx] = best;
}
return ans;
}
};
标签:int,lc1847,房间,vn,st,最近,rooms,auto,id
From: https://www.cnblogs.com/chenfy27/p/18076945