区间/Multiset-Codeforces 1029C Maximal Intersection

落日映苍穹つ 2022-05-15 10:08 313阅读 0赞

  • 区间/Multiset-Codeforces 1029C Maximal Intersection

  • 题目链接：

C. Maximal Intersection

  • 思路：

题目大意：

给定N个区间，求去掉一个区间后的最大交集长度为？

题解：

首先?N个区间的交集长度怎么求？

N个区间的交集长度=所有区间右端点的最小值 - 所有区间左端点的最大值

如果结果为负值，N个区间无交集

所以，每次都去掉一个区间对N-1个区间求交集，找出最大的交集长度

涉及删除排序，推荐set，但set中元素不能重复，改用multiset，采用两个multi分别存左端点和右端点

每次删除一个区间，求N-1个区间的交集

注意有坑：

multiset的erase() 函数需要以迭代器为参数，如果参数为数值，会删除容器中所有该数值

删除后，计算完N-1个区间的交集长度，记得把删除的区间再放进去

  • 代码：

    include

    include

    include

    using namespace std;

    define MAX_SIZE 300005

    multiset Left,Right;
    int L[MAX_SIZE],R[MAX_SIZE];

    int main()
    {

    1. int n;
    2. while(cin>>n)
    3. {
    4.     int Res=0;
    5.     for(int i=1;i<=n;i++)
    6.     {
    7.         scanf("%d%d",&L[i],&R[i]);
    8.         Left.insert(L[i]);
    9.         Right.insert(R[i]);
    10.     }
    11.     for(int i=1;i<=n;i++)
    12.     {
    13.         Left.erase(Left.find(L[i]));  //删除区间
    14.         Right.erase(Right.find(R[i]));
    15.         Res=max(Res,*(Right.begin())-*(Left.rbegin()));  //计算交集长度并保存最大值
    16.         Left.insert(L[i]);   //删除的区间重新塞回
    17.         Right.insert(R[i]);
    18.     }
    19.     Left.clear();
    20.     Right.clear();
    21.     cout<<Res<<endl;
    22. }
    23. return 0;

    }

发表评论

表情：
评论列表 （有 0 条评论，313人围观）

还没有评论，来说两句吧...

相关阅读

    相关 sicily 1029

    思路：首先创建两个函数operate() 和cycle()，其中operate()求得两个大数之和，cycle()将数组向后平移一位。首先初始化数组num，数组num存储兔子的

    素颜马尾好姑娘i素颜马尾好姑娘i/ 0 赞/ 259 阅读

    相关 URAL 1029

    题目大意：M层N列的矩阵（各元素均为正整数），找出一个路径从第一层到达第M层，使得路径上的所有数的和是所有可达路径中最小的，每次上到下一层以后就不能再上去，依次输出路径上的各点

    清疚清疚/ 0 赞/ 370 阅读