Hướng dẫn giải của [200 đề thầy Đức] Bài 180: Phủ đoạn thẳng
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Trong n đoạn thẳng, tìm đoạn thẳng bao trùm tất cả n-1 đoạn còn lại. Đoạn [a, b] bao trùm đoạn [c, d] khi a ≤ c ≤ d ≤ b. Nếu không có đoạn nào như vậy thì in -1. Đề đảm bảo không có hai đoạn trùng cả hai đầu mút nên đáp án (nếu có) là duy nhất.
Sub 1: Vét cạn — ~O(N^2)~
Với mỗi đoạn i, kiểm tra từng đoạn j ≠ i xem có thỏa L[i] ≤ L[j] và R[j] ≤ R[i] hay không. Nếu đúng với mọi j thì i là đáp án. Với n ≤ 100 cách này đã đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<long long> L(n), R(n);
for (int i = 0; i < n; i++) cin >> L[i] >> R[i];
// Vét cạn: với mỗi đoạn i, kiểm tra xem nó có bao trùm mọi đoạn j còn lại không
int ans = -1;
for (int i = 0; i < n && ans == -1; i++) {
bool ok = true;
for (int j = 0; j < n && ok; j++) {
if (j == i) continue;
if (!(L[i] <= L[j] && R[j] <= R[i])) ok = false;
}
if (ok) ans = i + 1;
}
cout << ans << "\n";
return 0;
}
Sub 2: Dùng giá trị cực trị — ~O(N)~
Nếu đoạn i bao trùm mọi đoạn khác thì L[i] phải là giá trị nhỏ nhất trong các L, và R[i] phải là giá trị lớn nhất trong các R. Ngược lại, nếu có đoạn nào có L nhỏ nhất và R lớn nhất thì nó bao trùm tất cả. Vì vậy ta tìm minL và maxR rồi kiểm tra có đoạn nào mang đúng cả hai giá trị đó hay không.
Bẫy cần chú ý: tọa độ có thể âm, dùng long long cho an toàn; khi không có đoạn nào thỏa thì in -1. Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<long long> L(n), R(n);
for (int i = 0; i < n; i++) cin >> L[i] >> R[i];
// Đoạn bao trùm mọi đoạn khác phải có L nhỏ nhất và R lớn nhất
long long minL = *min_element(L.begin(), L.end());
long long maxR = *max_element(R.begin(), R.end());
int ans = -1;
for (int i = 0; i < n; i++) {
if (L[i] == minL && R[i] == maxR) {
ans = i + 1; // đề đảm bảo không có hai đoạn trùng cả hai đầu nên chỉ có một đáp án
break;
}
}
cout << ans << "\n";
return 0;
}
Bình luận