【CodeForces】1029 - C Maximal Intersection (Multiset 多重集)

题目链接

题意：在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)); //注意如果不用find函数是不对的。 rs.erase(rs.find(v[i].second)); ans = max(ans,*rs.begin() - *ls.rbegin()); //保证重合 ls.insert(v[i].first); //reinsert rs.insert(v[i].second); } printf("%d\n", ans); return 0; }