本文共 1052 字,大约阅读时间需要 3 分钟。
题意:
求两条线段的最大重叠
思路:
按照l升序,r降序排列
维护最大的r
代码:
#include #include #include #include #include #include #include #include #include #include #include #include #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 PI;typedef pair 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 = 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;}
转载于:https://www.cnblogs.com/wrjlinkkkkkk/p/10428697.html