当前位置：首页 > news >正文

[H贪心] lc100376. 新增道路查询后的最短距离 II(贪心+读题+代码实现+周赛409_3)

news 来源：原创 2024/9/20 0:01:08

文章目录

- 1. 题目来源
- 2. 题目解析

1. 题目来源

链接：100376. 新增道路查询后的最短距离 II

2. 题目解析

被题目所蒙蔽了…

以为是最短路算法，或者是堆优化 dij 又有什么神奇的性质被我遗忘了？或者是最短路树？…

结果没读好题目，题目说明 query 的所有查询是不会有相交但不包含的关系的。也就是说，所有的查询，要么不想交，要么将包含一些小区间在里面。

那么思路就比较明确了，当遇见一个大的 query 区间，只需要将这个大 query 区间中的所有小区间全部弹出即可，因为步长是 1，所以有效的区间个数即为最短路长度。

时间复杂度： $O ((n + q) l o g n)$
空间复杂度： $O (n)$

class Solution {
public:vector<int> shortestDistanceAfterQueries(int n, vector<vector<int>>& queries) {set<pair<int, int>> S;for (int i = 1; i < n; i ++ ) S.insert({i - 1, i});vector<int> res;for (auto q : queries) {int l = q[0], r = q[1];auto it = S.lower_bound({l, -1});   // 直接找到 小于 [l, ] 左端点的区间// 如果找到了，且找到区间和查询区间同起点，且包含里面的小区间时// it->first == l 这个条件是一个优化条件，如果同起点的话，可能该区间还没被删除过// 但是不同起点的话，且还在我右边界内的点，肯定是被删除了的，就不用再进去判断了// 但是不能将 it->second < r 这个条件删除。不然就会进入 if 判断，S 将 insert 一个区间包含 的 子区间，答案增多一个if (it != S.end() && it->first == l && it->second < r) {// 将这些小区间全部剔除while (it != S.end() && it->first < r) it = S.erase(it);// 将查询区间插入S.insert({l, r});}res.push_back(S.size());}return res;}
};

class Solution {
public:vector<int> shortestDistanceAfterQueries(int n, vector<vector<int>>& queries) {vector<int> d(n), ans(queries.size());iota(d.begin(), d.end(), 0);for (int i = 0; i < queries.size(); i++) {auto l = upper_bound(d.begin(), d.end(), queries[i][0]);auto r = lower_bound(d.begin(), d.end(), queries[i][1]);if (l <= r) d.erase(l, r);ans[i] = d.size() - 1;}return ans;}
};