题解·Too Many Segments (easy version)

Handezheng · 2024-07-18 11:26:57 · 题解

题目传送门

前言:

前置芝士

做完的可以去做 CF1249D1 Too Many Segments (hard version)，它是本题的加强版，我在本题中思路的实现和代码均是参考它的数据范围的。

思路

题目要求我们删除一部分线段使得没有“坏点”的存在，那我们肯定要遍历一遍区间，找到哪个点是“坏点”后，才能进行操作。

当我们枚举到一个点时，如果这个点是“坏点”，那它肯定被多条线段所覆盖，枚举到这个点时，它前面的点一定都不是“坏点”（本来就不是“坏点”或在前面已经删掉一些线段使它不是“坏点”）。
那么当前覆盖这个点的线段的左端点对其毫无用处，无论删除多少条线段都不会改变这个点左面所有点是不是“坏点”，那我们可以关注右端点：

贪心地想，一条线段的右端点越“远”，那它就对更多的点有影响（贡献越大）。
所以，我们应该尽量删除右端点更靠右的线段。

细节及实现

实现

数据范围：n \le 200 并且 l,r\le 200，我们遍历区间所有点只需要花费 O(r_{max}) 的时间复杂度，所以就可以再花费 O(n) 的复杂度来枚举所有线段了。
但对于加强版，有 n \le 2\cdot10^5 且 l,r\le 2\cdot10^5，明显上述做法的时间会爆掉。
考虑优化。我们可以用一个数据结构来存储覆盖到当前点的线段，考虑到要需要用排序维护右端点更靠右，最好用 priority_queue 或 set（我个人推荐用 set,因为 priority_queue 仅支持 priority_queue.top() 的删除）。
遍历到一个点时，可能会有多条线段以它为左端点，所以我们可以用二维的 vector 来存储线段的有关信息。

细节

题目要求输出线段的编号，所以我们的 set 和 vector 都是结构体，包括线段右端点和线段编号。
在遍历到一个新的点时，我们要把右端点小于当前点的线段删掉（容易想到这样的点已经“过期”了，对后续操作无用）。
我们在删除线段时仅保证右端点尽量大，不保证它的编号是升序的，所以要对 ans 数组进行排序（以编号为关键字）。
~~感谢 STL 库~~ set 中有一个不常用的功能：set.rbegin() 指 set.end() 的前一个位置，在本题中就是右端点最大点所在的位置。
set.begin()，set.rbegin() 等返回的都是元素所在的位置，使用时应加上符号“*”。
AC code

~~应该有部分读者最喜欢看这个，所以把它安排在最后~~

这份代码在加强版中也是可以通过的。~~双倍经验~~

#include<bits/stdc++.h>
#include<vector>
#include<set>
using namespace std;
#define int long long
#define re register
#define F(j,i,n)  for(re int i = j;i <= n;i++)
const int N = 2e5 + 50,M = 1e3 + 50;
inline void read(int &x){
    re int f = 1;x = 0;
    re char s = getchar();
    while(s < '0' || s > '9'){
        if(s == '-') f = -1;
        s = getchar();
    }while(s >= '0' && s <= '9')
        x = x * 10 + s - '0',s = getchar();
    x *= f;
}

int n,k;
int tot;//被删除线段的数量 
struct node{
    int r,id;
    //r记录区间的右端点
    //id记录当前区间的编号
}ans[N];//被删除线段的编号 
inline bool operator < (node a,node b){
    if(a.r == b.r) return a.id < b.id;
    return a.r < b.r;
    //以右端点为关键字
}
inline bool cmp(node a,node b){
    return a.id < b.id;
    //以编号为关键字升序排序
}
vector <node> a[N];
//a[l]记录以l为左端点的线段的相关信息 
set <node> st;
//set记录覆盖到当前点的线段 

signed main(){

    read(n),read(k);
    int l,r;
    node tmp;
    F(1,i,n){
        read(l),read(r);
        tmp.r = r,tmp.id = i;
        a[l].push_back(tmp);
    }

    F(1,i,200000){
        while(st.size() && (*st.begin()).r < i){//区间的右端点小于当前点，说明这个区间已"过期"
            st.erase(*st.begin());
        }//删除"过期"的区间

        for(int j = 0;j < a[i].size();j ++){
            st.insert(a[i][j]);
        }//把以当前遍历到的点为左端点的区间插入至set

        while(st.size() > k){//如果这个点是坏点
            ans[++ tot] = *st.rbegin();//记录要被删除的区间
            st.erase(*st.rbegin());//删除区间
        }
    }
    printf("%lld\n",tot);
    sort(ans + 1,ans + tot + 1,cmp);
    F(1,i,tot) printf("%lld ",ans[i].id);

    return 0;
}

最后

如果有代码、思路问题，错别字问题及其他问题欢迎私聊

题解·Too Many Segments (easy version)

题目传送门

前言:

思路

细节及实现

实现

细节

AC code

最后