1 条题解
-
2
问题可以简化为：一条数轴上覆盖有 n 条线段 [ai,bi] ，需要算出去掉一条线段后，剩余线段可以覆盖的最大长度。其中ai,bi的范围为0~10^9。
思路分析：若是线段a与线段b之间，存在公共部分c，那么去除线段a，剩余线段的覆盖长度就为总长度减去a减c的差，换句话说，如果去除了任意一条线段a，剩余线段的总覆盖长度就为总覆盖长度减去a单独覆盖的长度。
根据这个结论，只要求出总长度和每条线段单独覆盖的长度，就能算出删去一条线段后，能覆盖的最长长度了。用差分算出每个位置被覆盖的次数，计算前缀和算出总覆盖长度，同时特判覆盖次数为1的位置，方便计算每条线段单独覆盖的长度，最后枚举每条线段，求出最大值即可，其中因为ai,bi的范围为0~10^9，还需需要对数据离散化处理。
参考代码
#include <bits/stdc++.h> using namespace std; int n; struct nod { int l, r; } cw[100005]; int b[300005], cnt, cc[300005]; int sum[800005]; int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> cw[i].l >> cw[i].r; b[++cnt] = cw[i].r; cw[i].r--; b[++cnt] = cw[i].l; b[++cnt] = cw[i].r; } sort(b + 1, b + 1 + cnt); int tot = unique(b + 1, b + 1 + cnt) - b;//对数组离散化 for (int i = 1; i <= n; i++) { cw[i].l = lower_bound(b + 1, b + 1 + tot, cw[i].l) - b; cw[i].r = lower_bound(b + 1, b + 1 + tot, cw[i].r) - b; cc[cw[i].l]++;//差分 cc[cw[i].r + 1]--; } int cov = 0; for (int i = 1; i <= tot; i++) { cc[i] += cc[i - 1]; if (cc[i])//被覆盖，计入总长度 cov += b[i + 1] - b[i]; if (cc[i] == 1)//恰好覆盖1次 sum[i] = b[i + 1] - b[i]; sum[i] += sum[i - 1]; } int ans = 0; for (int i = 1; i <= n; i++) ans = max(ans, cov - (sum[cw[i].r] - sum[cw[i].l - 1]));//总长度 - 恰好覆盖一次 cout << ans; }
hetaowjl
LV 1
SU
@ 2024-4-11 18:54:04
- 1