题意:
求两条线段的最大重叠
思路:
按照 l 升序, r 降序排列
维护最大的 r
代码:
- #include<iostream>
- #include<cstdio>
- #include<algorithm>
- #include<cstring>
- #include<string>
- #include<stack>
- #include<queue>
- #include<deque>
- #include<set>
- #include<vector>
- #include<map>
- #include<functional>
- #define fst first
- #define sc second
- #define pb push_back
- #define mem(a,b) memset(a,b,sizeof(a))
- #define lson l,mid,root<<1
- #define rson mid+1,r,root<<1|1
- #define lc root<<1
- #define rc root<<1|1
- #define lowbit(x) ((x)&(-x))
- using namespace std;
- typedef double db;
- typedef long double ldb;
- typedef long long ll;
- typedef unsigned long long ull;
- typedef pair<int,int> PI;
- typedef pair<ll,ll> PLL;
- const db eps = 1e-6;
- const int mod = 1e9+7;
- const int maxn = 2e6+100;
- const int maxm = 2e6+100;
- const int inf = 0x3f3f3f3f;
- int n;
- struct node{
- int l, r;
- };
- node a[maxn];
- bool cmp(node a, node b){
- if(a.l==b.l)return a.r> b.r;
- return a.l<b.l;
- }
- int main() {
- scanf("%d", &n);
- for(int i = 1; i <= n; i++){
- scanf("%d %d", &a[i].l,&a[i].r);
- }
- sort(a+1,a+1+n,cmp);
- int m = a[1].r;
- int ans = 0;
- for(int i = 2; i <= n; i++){
- if(m>= a[i].r){
- // 覆盖
- ans = max(ans, a[i].r-a[i].l);
- }
- else{
- // 相交, 不想交
- ans = max(ans, m-a[i].l);
- m = a[i].r;
- }
- }
- printf("%d",ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2967002.html