8-8作业/重写ren_gao_zu

ren_gao_zu · 2025-08-09 10:14:58 · 个人记录

作业

D4219 区间合并

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e5+5;
struct node{
    int l,r;
}a[N];
bool cmp(node x,node y){
    if(x.l==y.l){
        return x.r>y.r;
    }return x.l<y.l;
}
int n,ans;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].l>>a[i].r;
    }sort(a+1,a+n+1,cmp);
    int r1=a[1].r,l1=a[1].l;
    for(int i=2;i<=n;i++){
        if(a[i].l<=r1)r1=max(a[i].r,r1);
        else{
            printf("no");
            return 0;
        }
    }printf("%d %d",l1,r1);
    return 0;
}

P2434 [SDOI2005] 区间

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e6+5;
struct node{
    int l,r;
}a[N];
bool cmp(node x,node y){
    if(x.l==y.l)return x.r>y.r;
    return x.l<y.l;
}
int n,ans;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i].l>>a[i].r;
    sort(a+1,a+n+1,cmp);
    int l1=a[1].l,r1=a[1].r;
    for(int i=2;i<=n;i++){
        if(a[i].l<=r1)r1=max(a[i].r,r1);
        else{
            cout<<l1<<" "<<r1<<endl;
            l1=a[i].l,r1=a[i].r;
        }
    }cout<<l1<<" "<<r1;
    return 0;
}

重写

P1496 火烧赤壁

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e5+5;
struct node{
    int l,r;
}a[N];
bool cmp(node x,node y){
    return x.l<y.l;
}
int n,ans;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i].l>>a[i].r;
    sort(a+1,a+n+1,cmp);
    int l1=a[1].l,r1=a[1].r;
    for(int i=2;i<=n;i++){
        if(r1<=a[i].l){
            ans+=r1-l1;
            l1=a[i].l;
            r1=a[i].r;
        }
        else{
            r1=max(a[i].r,r1);
        }
    }cout<<ans+r1-l1;
    return 0;
}

P1668 [USACO04DEC] Cleaning Shifts S

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e6+5;
int t,n;
struct node{
    int l,r;
}a[N];
int ans=1;
bool cmp(node x,node y){
    if(x.l==y.l)return x.r>y.r;
    return x.l<y.l;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>t;
    for(int i=1;i<=n;i++)cin>>a[i].l>>a[i].r;
    sort(a+1,a+n+1,cmp);
    if(a[1].l>1){
        cout<<-1;
        return 0;
    }
    int la=a[1].r+1;

    for(int i=2;i<=n;i++){
        if(a[i].l>la){
            cout<<-1;
            return 0;
        }
        if(a[i].r<la)continue;
        else{
            int id,ma=0;
            for(int j=i;j<=n;j++){
                if(a[j].l>la)break;
                else{
                    if(ma<a[j].r){
                        ma=a[j].r;
                        id=j;
                    }
                }
            }
            if(ma>=t){
                cout<<ans+1;
                return 0;
            }
            la=a[id].r+1,ans++;
        }

    }
    if(la<=t)cout<<-1;
    else cout<<ans;
    return 0;
}