首页 > 其他分享 >lc1847 最近的房间

lc1847 最近的房间

时间:2024-03-16 12:55:05浏览次数:36  
标签:int lc1847 房间 vn st 最近 rooms auto id

有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

相关文章

  • 代码随想录 第21天 | ● 530.二叉搜索树的最小绝对差 ● 501.二叉搜索树中的众数 ●
    leetcode:530.二叉搜索树的最小绝对差-力扣(LeetCode)思路:判断最小绝对差,肯定用中序遍历,双指针一前一后依次判断。classSolution{intresult=Integer.MAX_VALUE;TreeNodepre=null;publicintgetMinimumDifference(TreeNoderoot){if(root==......
  • 236. 二叉树的最近公共祖先c
    /***Definitionforabinarytreenode.*structTreeNode{*intval;*structTreeNode*left;*structTreeNode*right;*};*/structTreeNode*lowestCommonAncestor(structTreeNode*root,structTreeNode*p,structTreeNode*q){......
  • 2024-03-13:用go语言,给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 输
    2024-03-13:用go语言,给定一个二叉搜索树,找到该树中两个指定节点的最近公共祖先。输入:root=[6,2,8,0,4,7,9,null,null,3,5],p=2,q=8。输出:6。答案2024-03-13:来自左程云。灵捷3.5大体步骤如下:1.首先,我们需要遍历树来找到这两个节点。从根节点开始,若两个节点都比......
  • 43. 实现休息房间的逻辑
    本节目标实现休息房间可以回一次血,实现宝箱房间可以获得卡牌实现办法休息房间回血添加一个RestRoomPanel,给它挂上UI和脚本代码实现如下usingSystem;usingUnityEngine;usingUnityEngine.UIElements;publicclassRestRoomPanel:MonoBehaviour{privateV......
  • 代码随想录算法训练营day21 | leetcode 530. 二叉搜索树的最小绝对差、501. 二叉搜索
    目录题目链接:530.二叉搜索树的最小绝对差-简单题目链接:501.二叉搜索树中的众数-简单题目链接:236.二叉树的最近公共祖先-中等题目链接:530.二叉搜索树的最小绝对差-简单题目描述:给你一个二叉搜索树的根节点root,返回树中任意两不同节点值之间的最小差值。差值是一个正数,......
  • 并行化优化KD树算法:使用C#实现高效的最近邻搜索
    本文信息中文名:《并行化优化KD树算法:使用C#实现高效的最近邻搜索》英文名:"ParallelizedOptimizationofKD-TreeAlgorithm:ImplementingEfficientNearestNeighborSearchinC#"摘要本文介绍了如何使用并行计算技术优化KD树算法,并使用C#编程语言实现了高效的最近邻......
  • 类以撒的结合的房间生成算法
    类以撒的结合的房间生成算法原链接翻译版本目前本人只实现了房间大小都一样的情况,没有什么2x2,L型,2x1之类的房间放个效果图算法需要注意的房间选择对于当前位置是否有设置房间(是否被占位)当前房间位置是否越界(超出限定范围)当前位置的周围4方向的房间量是否大于1个(为什......
  • 235. 二叉搜索树的最近公共祖先c
     /***Definitionforabinarytreenode.*structTreeNode{*intval;*structTreeNode*left;*structTreeNode*right;*};*/structTreeNode*preorder(structTreeNode*root,structTreeNode*p,structTreeNode*q){if(!root)r......
  • 236. 二叉树的最近公共祖先c
    思想就是层次遍历,然后判断每个节点是否为父节点、/***Definitionforabinarytreenode.*structTreeNode{*intval;*structTreeNode*left;*structTreeNode*right;*};*/booljudge(structTreeNode*root,structTreeNode*q){if(......
  • 05. 生成房间之间连线
    画线使用了LineRenderer如上图所示,LineRenderer里面有两个点,分别是index0和index1,然后它还有线宽,我在我的屏幕上试了一下,0.05是一个粗细比较合适的线目前线是洋红色的,我们需要添加材质,才能让其有颜色。这边我们创建了一个材质这个材质使用了透明的Shader,然后使用了一......