【題解】Zerojudge f855 - 第 3 題 線段覆蓋長度 測資加強版

題目連結

題目大意

給定 $n$ 條線段，第 $i$ 條線段覆蓋 $[L_i, R_i]$ 區間。求線段聯集的長度。

• $1 \leq n < 10000$
• $0 \leq L_i \leq R_i < 10^7$

題解

我們先對所有線段按照 $L_i$ 由小到大排序，排序後兩個相鄰的線段 $i$ 和 $i + 1$ 的相交情況可以分成兩個 case：

1. $R_i < L_{i + 1}$：兩個線段沒有交集
2. $R_i \geq L_{i + 1}$：兩個線段重疊

我們用兩個變數維護當前的線段，如果 $i + 1$ 與當前的線段重疊，則更新線段的右界，否則把線段的長度加入答案，並把線段更新為 $L_i, R_i$。實作的細節請參考 code。本題的 code 拿去丟 b966 也是可以 AC 的。

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	vector<pair<int, int>> a(n);
	for(int i = 0; i < n; i++) {
		cin >> a[i].first >> a[i].second;
	}
	sort(a.begin(), a.end());
	int ans = 0;
	int L = -1, R = -1;
	for(auto [ll, rr] : a) {
		if(ll > R) {
			ans += R - L;
			L = ll, R = rr;
		} else {
			R = max(R, rr);
		}
	}
	ans += R - L;
	cout << ans << "\n";
	return 0;
}

如果本文對您有幫助的話幫忙點擊廣告和分享吧！

© 若無特別註明，本站文章皆由 WeakMouse's Coding Blog 原創 ，轉載引用本文前請先留言告知。本文轉載請註明文章源自 WeakMouse's Coding Blog ，作者 ，並附上原文連結： 【題解】Zerojudge f855 - 第 3 題 線段覆蓋長度 測資加強版