题目链接
题意:在x轴上有n条线段,给出它们的左右端点,求去掉其中一条后,剩下n-1条线段的最大重叠长度。
本来以为贪心能过的。。然后怎么都写不对,翻大佬的代码发现的一个没见过的容器 multiset,多重集。顾名思义,与 set 不同的就是,它可以存放重复的元素。然后利用multiset枚举删除的那条边就好了。
AC代码:
#include <bits/stdc++.h>
using namespace std;
int main(){
multiset <int> ls,rs;
int n;
scanf(
"%d ",&n);
vector<pair<int ,int > > v(n);
for(
int i=
0;i<n;++i){
scanf(
"%d %d",&v[i].first,&v[i].second);
ls.insert(v[i].first);
rs.insert(v[i].second);
}
int ans =
0;
for(
int i=
0;i<n;++i){
ls.erase(ls.find(v[i].first));
rs.erase(rs.find(v[i].second));
ans = max(ans,*rs.begin() - *ls.rbegin());
ls.insert(v[i].first);
rs.insert(v[i].second);
}
printf(
"%d\n", ans);
return 0;
}