为什么这能过?
查看原帖
为什么这能过?
1125463
_pig楼主2023/10/15 14:07
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e5+10;
struct node{
    int l,r;
}a[maxn];
int b[maxn];
bool cmp(node x,node y){
    if(x.l==y.l)return x.r<y.r;
    return x.l<y.l;
}
signed main(){
//    freopen("lifeguards.in","r",stdin);
//    freopen("lifeguards.out","w",stdout);
    int n; cin>>n;
    for(int i=1;i<=n;i++)scanf("%lld%lld",&a[i].l,&a[i].r);
    sort(a+1,a+n+1,cmp);
    int cnt=1,ans=0,sum=a[1].l;
    for(int i=1;i<=n;i++)b[i]=a[i].r-a[i].l;
    for(int i=1;i<=n;i++){
        int cmt=a[cnt].l;
        for(int j=cnt;j<=n;j++){
            if(j==i)continue;
            if(a[j].l>a[i].r)break;
            else if(a[j].r>=a[i].r && a[j].l>=a[i].l){
                b[i]-=(a[i].r-max(cmt,a[j].l));
                break;
            }
            else if(a[j].r>=a[i].r && a[j].l<=a[i].l){
                b[i]=0;
                break;
            }
            else if(a[i].l>a[j].r)cnt++;
            else if(a[j].r<a[i].r && a[i].l<a[j].l){
                if(a[j].l<=cmt && cmt<=a[j].r){
                    b[i]-=(a[j].r-cmt);
                    cmt=a[j].r;
                }
                else if(cmt<a[j].l){
                    b[i]-=(a[j].r-a[j].l);
                    cmt=a[j].r;
                }
            }
            else if(a[j].r<a[i].r && a[i].l>=a[j].l){
                if(a[j].l<=cmt && cmt<=a[j].r){
                    b[i]-=(a[j].r-max(a[i].l,cmt));
                    cmt=a[j].r;
                }
                else if(cmt<a[j].l){
                    b[i]-=(a[j].r-a[i].l);
                    cmt=a[j].r;
                }
            }
        }
    }
    sort(b+1,b+n+1);
    for(int i=1;i<=n;i++){
        if(a[i].r<sum)continue;
        else ans+=(a[i].r-max(sum,a[i].l));
        sum=max(sum,a[i].r);
    }
    cout<<ans-b[1];
	return 0;
}
2023/10/15 14:07
加载中...