AcWing 1343. 挤牛奶
原题链接
简单
作者:
luckdog
,
2024-03-14 09:16:38
,
所有人可见
,
阅读 8
//此题求的是区间合并后的最大长度以及区间中最大空缺的长度
#include<iostream>
#include<algorithm>
using namespace std;
typedef pair<int,int> PII;
const int N=5010;
int n;
PII segs[N]; //定义区间的数组
int main()
{
cin>>n;
for(int i=0;i<n;i++) cin>>segs[i].first>>segs[i].second;
sort(segs,segs+n); //将所有区间排序
int res1=0,res2=0; //定义第一问的答案和第二问的答案
int l=segs[0].first,r=segs[0].second; //l和r先指向第一个区间
for(int i=1;i<n;i++) //从第二个区间开始枚举
{
if(segs[i].first<=r) r=max(r,segs[i].second);
else{ //找到一个区间
res1=max(res1,r-l);
res2=max(res2,segs[i].first-r); //第二问的长度是当前区间(维护区间)的右端点和当前第i个左端点的距离
l=segs[i].first,r=segs[i].second; //更新当前维护的区间
}
}
res1=max(res1,r-l); //最后维护的区间也要更新
cout<<res1<<" "<<res2<<endl;
return 0;
}