Hướng dẫn giải của [2627 KS3_DE2] Câu 2: Xếp lịch phòng máy
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
Mỗi đăng ký là nửa khoảng ~[s, e)~. (A) Số đăng ký nhiều nhất xếp được vào một phòng. (B) Số phòng ít nhất là số đăng ký cùng diễn ra nhiều nhất tại một thời điểm.
Sub 1: vét cạn — ~O(2^n \cdot n)~ cho (A), ~O(n^2)~ cho (B), dùng khi ~n \le 15~
(A) thử mọi tập con không chồng nhau. (B) với mỗi đăng ký, đếm số khoảng chứa thời điểm ~s_i~. Nếu chỉ nộp sub này: đúng 7/20 test.
Sub 2: tham lam và quét sự kiện — ~O(n \log n)~
(A) sắp xếp theo ~e~ tăng dần, nhận đăng ký nếu ~s >= e~ của đăng ký đã nhận gần nhất. (B) tạo sự kiện ~(thời điểm, +1)~ và ~(thời điểm, -1)~, sắp xếp sao cho kết thúc (-1) xử lý trước bắt đầu (+1) cùng thời điểm. Đúng 20/20 test.
Chương trình hoàn chỉnh
main đọc t và từng ngày. Nếu ~n \le 15~ thì gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
// Moi dang ky la khoang nua mo [s, e). Yeu cau:
// (A) so dang ky nhieu nhat xep vao 1 phong (khong chong nhau);
// (B) so phong it nhat de nhan het n dang ky = so dang ky cung dien ra nhieu nhat tai mot thoi diem.
// Sub 1: vet can. (A) thu moi tap con (n <= 15). (B) voi moi dang ky, dem so khoang chua thoi diem s_i. O(n^2)
void sub1(const vector<pair<long long, long long>> &seg, long long &A, long long &B) {
int n = seg.size();
// conf[i]: mask cac dang ky chong len dang ky i
vector<int> conf(n, 0);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (i != j && seg[i].first < seg[j].second && seg[j].first < seg[i].second)
conf[i] |= 1 << j;
A = 0;
for (int mask = 0; mask < (1 << n); mask++) {
bool ok = true;
for (int i = 0; i < n && ok; i++)
if ((mask >> i & 1) && (conf[i] & mask)) ok = false;
if (ok) A = max(A, (long long)__builtin_popcount(mask));
}
B = 0;
for (int i = 0; i < n; i++) {
long long c = 0;
for (int j = 0; j < n; j++)
if (seg[j].first <= seg[i].first && seg[i].first < seg[j].second) c++;
B = max(B, c);
}
}
// Sub 2: (A) tham lam theo thoi diem ket thuc tang dan. (B) quet su kien: ket thuc (-1) xu ly truoc bat dau (+1) cung thoi diem.
void sub2(const vector<pair<long long, long long>> &seg, long long &A, long long &B) {
vector<pair<long long, long long>> v = seg;
sort(v.begin(), v.end(), [](const pair<long long, long long> &x, const pair<long long, long long> &y) {
return x.second < y.second;
});
A = 0;
long long last = LLONG_MIN;
for (auto &p : v)
if (p.first >= last) { A++; last = p.second; }
vector<pair<long long, int>> ev;
for (auto &p : seg) {
ev.push_back({p.first, +1});
ev.push_back({p.second, -1});
}
sort(ev.begin(), ev.end()); // (thoi diem, -1) truoc (thoi diem, +1)
long long cur = 0;
B = 0;
for (auto &e : ev) {
cur += e.second;
B = max(B, cur);
}
}
int main() {
freopen("CAU2.INP", "r", stdin);
freopen("CAU2.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<pair<long long, long long>> seg(n);
for (int i = 0; i < n; i++) cin >> seg[i].first >> seg[i].second;
long long A, B;
if (n <= 15) sub1(seg, A, B);
else sub2(seg, A, B);
cout << A << " " << B << "\n";
}
return 0;
}
Bình luận