挤牛奶

题目 挤牛奶

image-5bb138ea

思路分析

x~y y+1~z不做合并

那就是模版一样的情况

不过需要多维护一个数据

不仅要最大的区间长度 还要前一个合并完的区间和下一个区间之间的距离的最大值

这个距离需要有个特殊考虑 如果区间只有一个 就不存在所谓间距

代码实现

原模板15ms

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

typedef pair<int,int> PII;
vector<PII> milks;
int n;

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=0;i<n;i++){
        int l,r;cin>>l>>r;
        milks.push_back({l,r});
    }
    sort(milks.begin(),milks.end());

    int st=-1,ed=-1,last_ed=0;
    int res_y=0,res_n=0;
    int cnt=0;
    for(auto milk:milks){
        cnt++;
        if(ed<milk.first){
            if(ed!=-1){
                res_y=max(res_y,ed-st);
                last_ed=ed;//记录一下上个区间的结束是多少
            }
            st=milk.first,ed=milk.second;
            if(cnt>1)//如果只有一个区间 就不存在间隙 不做该步
                res_n=max(res_n,st-last_ed);
        }
        else if(ed<milk.second)
            ed=milk.second;
    }
    if(ed!=-1)
        res_y=max(res_y,ed-st);
    cout<<res_y<<" "<<res_n<<endl;
    return 0;
}

改进模板 15 ms

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

const int N=5010;
typedef pair<int,int> PII;
PII milks[N];
int cnt=0;
int n;

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=0;i<n;i++){
        int l,r;cin>>l>>r;
        milks[cnt++]={l,r};
    }
    sort(milks,milks+n);

    int st=-1,ed=-1,last_ed=0;
    int res_y=0,res_n=0;
    int count=0;
    for(int i=0;i<n;i++){
        count++;
        if(ed<milks[i].first){
            if(ed!=-1){
                res_y=max(res_y,ed-st);
                last_ed=ed;//记录一下上个区间的结束是多少
            }
            st=milks[i].first,ed=milks[i].second;
            if(count>1)//如果只有一个区间 就不存在间隙 不做该步
                res_n=max(res_n,st-last_ed);
        }
        else    ed=max(milks[i].second,ed);
    }
    if(ed!=-1)
        res_y=max(res_y,ed-st);
    cout<<res_y<<" "<<res_n<<endl;
    return 0;
}

同类题型

视频讲解

⬅️ 区间合并相关问题 🏠 00-刷题理模型 ➡️ 改变数组元素