codeforces 1249D1/D2 Too Many Segments （贪心）

题意说明

有n个区间，第i个区间覆盖范围[li,ri]内所有点，问删除最少哪些区间，使得所有点被区间覆盖的次数少于等于k次

解题思路

看到这个题的时候，觉得和开关（反转）问题很像，从左到右，每次尽量满足当前点需要满足的条件，二者的区别在于这个题目对同一个点的操作次数可能不止一次

这时候，我们就需要考虑这样的问题：如何让当前点x满足条件的同时，让右边的点x+1,x+2,...删除最少的区间以满足条件，答案很显然，我们每次删除覆盖x的区间中ri最大者，直到覆盖当前点x的区间数小于等于k，这样就可以保证删除最少的区间满足条件了

具体实现：

1）统计出以每个点x为左端点的区间，用vector记录

2）因为同一个区间可以覆盖多个点，即覆盖x的区间可能同时覆盖了x+1，x+2...等等，因此用set记录下覆盖当前点的所有区间，这样可以省去大量时间

3）若set中存储的区间个数大于k个，每次删除这些区间中右端点最大者（利用set自动排序的特点，我们对所有区间按右端点排序的话，可以很快地找到set中右端点最大者），并记录下来，直到set中的存储的区间个数小于等于k

4）输出删除的区间个数和区间编号

代码区

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<queue>

#include<string>

#include<fstream>

#include<vector>

#include<stack>

#include <map>

#include<set>

#include <iomanip>

#define bug cout << "**********" << endl

#define show(x, y) cout<<"["<<x<<","<<y<<"] "

#define LOCAL = 1;

using namespace std;

typedef long long ll;

const ll inf = 1e18 + ;

const int Max = 2e5 + ;

struct Node

{

    int r;

    int id;

    bool operator<(const Node &node) const

    {

        if (r != node.r)

            return r < node.r;

        return id < node.id;

    }

};

int n, k;

int sum = ;

vector<Node> node[Max];

vector<int> num;

set<Node> s;

int main()

{

#ifdef LOCAL

//    freopen("input.txt", "r", stdin);

//    freopen("output.txt", "w", stdout);

#endif

    sum = ;

    scanf("%d%d", &n, &k);

    for (int i = , l, r; i <= n; i++)

    {

        scanf("%d%d", &l, &r);

        Node now;

        now.r = r;

        now.id = i;

        sum = max(sum, r);

        node[l].push_back(now);

    }

    for (int i = ; i <= sum; i++)

    {

        while (!s.empty() && (*s.begin()).r < i)

            s.erase(s.begin());

        for (int j = ; j < node[i].size(); j++)

            s.insert(node[i][j]);

        while (s.size() > k)

        {

            num.push_back((*s.rbegin()).id);

            s.erase(*s.rbegin());

        }

    }

    sort(num.begin(), num.end());

    printf("%d\n",num.size());

    for (int i = ; i < num.size(); i++)

        printf("%d%c", num[i], i == num.size() -  ? '\n' : ' ');

    return ;

}

巴特西

codeforces 1249D1/D2 Too Many Segments （贪心）

题意说明

解题思路

代码区

最新文章

热门文章