【題目敘述】https://zerojudge.tw/ShowProblem?problemid=b966
【解題想法】排序 【筆記】【筆記】
【Tag】排序、貪心、掃描線
- {a, b}：每個線段的「起點」座標 a 和「終點」座標 b。
- 排序：a 由小到大排序，a 相同的話，b 由大到小排序。
- 變數 s：目前線段的「起點」座標。
- 變數 e：目前線段的「終點」座標。
【做法-1】掃描線的概念
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;
#define pii pair<int,int>
#define F first
#define S second
bool cmp(pii a, pii b) {
if (a.first == b.first) {
return a.second > b.second;
} else {
return a.first < b.first;
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int N, a, b;
while (cin >> N) {
vector<pii> v;
for (int i=0; i<N; i++) {
cin >> a >> b;
v.push_back({a, b});
}
sort(v.begin(), v.end(), cmp);
int s=0, e=0, ans=0;
for (int i=0; i<v.size(); i++) {
if (v[i].F >= e) {
ans += (e-s);
s = v[i].F;
e = v[i].S;
} else if (v[i].S > e) {
e = v[i].S;
}
}
ans += (e-s);
cout << ans << endl;
}
return 0;
}
【做法-2】換個角度思考
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
int N, L, R;
cin >> N;
vector<pair<int,int>> v;
for (int i = 0; i < N; i++) {
cin >> L >> R;
//把線段的開始端點和結束端點視為獨立的evnet
//在線段的開始端點L處，event +1
v.push_back({L, 1});
//在線段的結束端點R處，event -1
v.push_back({R, -1});
}
sort(v.begin(), v.end());
//now指向目前檢視的event
//event為該座標點i, 對應一個左閉由開區間[i, i+1), 共被幾段線段覆蓋
int now = 0, event = 0, ans = 0;
for (int i = 0; i <= 1e7; i++) {
while (now < (int)v.size() && v[now].first == i) {
event += v[now].second;
now++;
}
if (event > 0) {
ans++;
}
}
cout << ans << "\n";
return 0;
}
while True:
try:
n = int(input())
lst = []
for i in range(n):
l, r = map(int, input().split())
lst.append([l, r])
lst.sort(key = lambda x:(x[0], x[1]))
for i in range(1, len(lst)):
if lst[i][1] < lst[i-1][1]:
lst[i] = lst[i-1]
lst[i-1] = []
elif lst[i-1][1] < lst[i][0]:
continue
else:
lst[i][0] = lst[i-1][0]
lst[i-1] = []
count = 0
for part in lst:
if part != []:
count += (part[1]-part[0])
print(count)
except:
break