CF1249D1 题解

· · 题解

CF1249D1 Too Many Segments (easy version) 题解

原题链接

题目描述

给定 n 个区间以及一个数字 k，每对 l,r 覆盖的区间会 +1，求至少要删除多少个区间才能使得每个位置的值都不超过 k，输出删除的最小个数 m 及删除的方案。

做法

看到数据范围 n \le200，我们可以接受 O(n^3) 的做法。

首先我们处理区间加减，这一点可以使用差分数组实现，我们在需要修改开头 l 位置 +1，在结尾 r + 1 位置 -1。因为可以接受 O(n^3)，所以也可以直接暴力修改。

我们直接枚举每个位置，看每个位置上该点是否符合条件，如果不符合条件，那么我们优先删除包含当前点，未被删除，右端点尽可能大的区间。

为什么要右端点尽可能大呢？

我们考虑当前枚举到 i 那么它前面的所有点一定都符合条件，所以我们应该让删除的区间尽可能包含更多后面的点，显然这样更优。于是我们直接把所有区间按照右端点排序，然后暴力枚举判断即可。

这样外层枚举位置 i，内层枚举区间并暴力删除，这样最劣的复杂度是 O(n^3) 的，可以通过。

同时我们可以使用差分优化掉暴力修改的一维，时间复杂度为 O(n^2)。

但是显然在加强版中还是无法通过，所以还可以继续优化下去，我们分析可以知道代码主要的复杂度在枚举每一个区间上面。我们考虑怎么样避免枚举的复杂度。

这时候就需要使用数据结构及一些技巧了。

我们考虑既然从左到右判断每个点，那么当我们把整个区间都按照 l 值从左到右排序，那么每次这个点只会使用到左端点小于它的区间。

同时我们要使得右端点尽可能的大，所以我们可以维护出一个优先队列。我们在优先队列中按照区间的右端点排序，这样每次取出堆顶都是满足条件的右端点最大的区间，我们再差分删除这个区间即可。

这样外层枚举位置为 O(V)（值域），内层优先队列为 O(\log n)。由于值域 V 和 n 同阶，所以复杂度为 O(n \log n)，足够通过强化版本。

AC Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int maxn = 2e5 + 10;
struct note{
    int l,r,id;
}se[maxn];

bool cmp(note a,note b)
{
    return a.l < b.l;
}

struct ccmp{
    inline int operator () (const note &a,const note &b) const
    {
        return a.r < b.r;
    }
};

int d[maxn];
priority_queue<note,vector<note>,ccmp> q;
vector<int> ans;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0); 
    int n,k;
    cin >> n >> k;
    for(int i = 1;i <= n;i++)
    {
        cin >> se[i].l >> se[i].r;
        se[i].id = i;
        d[se[i].l]++;
        d[se[i].r + 1]--;
    }
    sort(se + 1,se + n + 1,cmp);
    int now = 1;
    int cnt = 0;
    for(int i = 1;i <= 2e5;i++)
    {
        d[i] += d[i - 1];
        while(now <= n && se[now].l <= i)
        {
            q.push(se[now]);
            now++;
        }
        while(d[i] > k && !q.empty())
        {
            note p = q.top();
            q.pop();
            d[i]--;
            d[p.r + 1]++;
            cnt++;
            ans.push_back(p.id);
        }
    }
    cout << cnt << endl;
    for(int i = 0;i < cnt;i++) 
    {
        cout << ans[i] << " ";
    }
    return 0;
}

如果想要看强化（数据范围较大）版本，请移步CF1249D2 Too Many Segments (easy version)。

感谢阅读，希望对你有所帮助。