AtCoder Grand Contest 040 B

传送门

一看就感觉很贪心

考虑左端点最右的区间 $p$ 和右端点最左的区间 $q$

如果 $p,q$ 属于同一个集合（设为 $S$，另一个集合设为 $T$），那么其他的区间不管是不是在 $S$ 都不会影响 $S$ 的交集大小

那么为了最优显然我们只要留一个最长的区间给 $T$ ，然后其他全给 $S$

代码实现的时候枚举不属于 ${p,q}$ 的最长区间时也可以考虑 $p,q$ 的区间长度，并不影响答案

然后考虑 $p,q$ 不属于同一个集合的情况，不妨设 $p$ 在 $S$ ， $q$ 在 $T$

设第 $i$ 个区间的左端点为 $L[i]$，右端点为 $R[i]$

那么答案为 $max(0,min_{i \in S} (R[i]) -L[p])+max(0,R[q]-max_{i \in T}(L[i]))$

现在问题就是求这个式子的最大值

把区间按 $L$ 排序，枚举 $k$ ，把前 $k$ 名的区间给 $T$ ，剩下给 $S$

这样即可保证枚举到式子 $max(0,R[q]-max_{i \in T}(L[i]))$ 中的 $max_{i \in T}(L[i])$ 的所有情况

具体维护的话就预处理前缀后缀 $min,max$ 即可

代码实现的时候同样可以不用强制 $p,q$ 不属于同一个集合，因为不影响答案

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<vector>

using namespace std;

typedef long long ll;

inline int read()

{

    int x=,f=; char ch=getchar();

    while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }

    while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }

    return x*f;

}

const int N=2e5+,INF=1e9;

int n,ans;

struct dat {

    int l,r;

    dat (int _l=,int _r=) { l=_l,r=_r; }

    inline bool operator < (const dat &tmp) const {

        return l!=tmp.l ? l<tmp.l : r<tmp.r;

    }

}d[N];

int lx[N],rx[N],ly[N],ry[N];

int main()

{

    n=read();

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

        d[i].l=read(),d[i].r=read();

    sort(d+,d+n+);

    lx[]=d[].l,rx[]=d[].r;

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

    {

        lx[i]=max(lx[i-],d[i].l);

        rx[i]=min(rx[i-],d[i].r);

    }

    ly[n]=d[n].l; ry[n]=d[n].r;

    for(int i=n-;i>=;i--)

    {

        ly[i]=max(ly[i+],d[i].l);

        ry[i]=min(ry[i+],d[i].r);

    }

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

        ans=max(ans,max(,rx[i]-lx[i]+)+max(,ry[i+]-ly[i+]+));

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

        ans=max(ans,d[i].r-d[i].l++max( , min(ry[i+],rx[i-])-max(ly[i+],lx[i-])+ ));

    printf("%d\n",ans);

    return ;

}

巴特西

AtCoder Grand Contest 040 B - Two Contests

最新文章

热门文章