区间/Multiset-Codeforces 1029C Maximal Intersection

落日映苍穹つ 2022-05-15 10:08 202阅读 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<iostream>
    #include<cstdio>
    #include<set>
    using namespace std;
    #define MAX_SIZE 300005
    multiset<int> Left,Right;
    int L[MAX_SIZE],R[MAX_SIZE];
    
    int main()
    {
        int n;
        while(cin>>n)
        {
            int Res=0;
            for(int i=1;i<=n;i++)
            {
                scanf("%d%d",&L[i],&R[i]);
                Left.insert(L[i]);
                Right.insert(R[i]);
            }
            for(int i=1;i<=n;i++)
            {
                Left.erase(Left.find(L[i]));  //删除区间
                Right.erase(Right.find(R[i]));
                Res=max(Res,*(Right.begin())-*(Left.rbegin()));  //计算交集长度并保存最大值
                Left.insert(L[i]);   //删除的区间重新塞回
                Right.insert(R[i]);
            }
            Left.clear();
            Right.clear();
            cout<<Res<<endl;
        }
        return 0;
    }

[C. Maximal Intersection]: http://codeforces.com/problemset/problem/1029/C