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

xiaoxiao2021-03-01  38

题目链接

题意:在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; }
转载请注明原文地址: https://www.6miu.com/read-4200057.html

最新回复(0)