Hướng dẫn giải của Câu 4 (đề Bình Dương 2021)
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
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.
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
Chọn nhiều trò chơi nhất sao cho các khoảng thời gian không trùng nhau: bài chọn khoảng không giao nhau nhiều nhất. Chương trình coi hai khoảng chỉ chạm nhau tại một điểm là trùng nhau (đề không nói rõ điểm này).
Sub 1: Vét cạn - ~O(2^n \cdot n^2)~, dùng khi ~n \le 15~
Thử mọi tập con, kiểm tra từng cặp có không giao nhau không. Nếu chỉ nộp sub này: đúng 6/28 test.
Sub 2: Tham lam - ~O(n \log n)~
Sắp theo thời điểm kết thúc tăng dần, chọn trò chơi kết thúc sớm nhất mà bắt đầu sau khi trò chơi đã chọn trước đó kết thúc. Đúng 28/28 test.
Chương trình hoàn chỉnh
main đọc N và các khoảng. Nếu ~n \le 15~ gọi sub1, còn lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int n;
vector<long long> a, b;
// Hai tro choi [a,b] va [c,d] trung nhau neu khong (b < c hoac d < a).
// Sub 1: vet can 2^n tap con, voi moi tap kiem tra cac cap deu khong trung nhau. Dung khi n <= 15.
void sub1() {
int best = 0;
for (int mask = 0; mask < (1 << n); mask++) {
bool ok = true;
for (int i = 0; i < n && ok; i++) {
if (!((mask >> i) & 1)) continue;
for (int j = i + 1; j < n && ok; j++) {
if (!((mask >> j) & 1)) continue;
if (!(b[i] < a[j] || b[j] < a[i])) ok = false;
}
}
if (ok) best = max(best, __builtin_popcount(mask));
}
cout << best << "\n";
}
// Sub 2: tham lam - sap theo thoi diem ket thuc tang dan, chon tro choi ket thuc som nhat
// ma bat dau sau khi tro choi truoc ket thuc. O(n log n).
void sub2() {
vector<int> idx(n);
for (int i = 0; i < n; i++) idx[i] = i;
sort(idx.begin(), idx.end(), [&](int x, int y) { return b[x] < b[y]; });
long long cur = LLONG_MIN;
int cnt = 0;
for (int i : idx) {
if (a[i] > cur) {
cnt++;
cur = b[i];
}
}
cout << cnt << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
a.resize(n);
b.resize(n);
for (int i = 0; i < n; i++) cin >> a[i] >> b[i];
if (n <= 15) sub1();
else sub2();
return 0;
}
Bình luận