Hướng dẫn giải của [200 đề thầy Đức] Bài 170: Số điểm đỗ tối thiểu
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 xe chiếm một chỗ từ lúc đến đến lúc đi. Cần tìm số chỗ tối thiểu, tức là số xe lớn nhất có mặt tại cùng một thời điểm. Quy ước theo bộ dữ liệu chấm: nếu xe đến đúng lúc có xe khác rời đi thì coi như chưa có chỗ trống, hai xe cùng chiếm chỗ tại thời điểm đó.
Sub 1: Vét cạn — ~O(n^2)~, dùng khi ~n \le 1000~
Số xe lớn nhất đạt được ngay tại một thời điểm có xe đến. Với mỗi xe ~i~, đếm số xe ~j~ thỏa ~A_j \le A_i \le B_j~. Nếu chỉ nộp sub này: đúng 22/42 test, các test lớn bị quá giờ.
Sub 2: Sắp xếp sự kiện — ~O(n \log n)~
Tạo danh sách sự kiện (thời điểm, loại), loại 0 là xe đến và loại 1 là xe đi. Sắp xếp rồi duyệt, cộng 1 khi gặp xe đến và trừ 1 khi gặp xe đi. Khi cùng thời điểm, xe đến đứng trước. Giờ dạng HHMM so sánh trực tiếp được như số nguyên. Nếu chỉ nộp sub này: đúng 42/42 test.
Chương trình hoàn chỉnh
main đọc ~T~ bộ dữ liệu. Với mỗi bộ, nếu ~n \le 1000~ thì gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int n;
int A[10005], B[10005]; // giờ đến, giờ đi (dạng HHMM, so sánh được như số nguyên)
// Sub 1: vét cạn O(n^2). Overlap lớn nhất đạt tại một thời điểm có xe đến.
// Xe j đang chiếm chỗ lúc A[i] nếu A[j] <= A[i] <= B[j].
void sub1() {
int best = 0;
for (int i = 0; i < n; i++) {
int cnt = 0;
for (int j = 0; j < n; j++)
if (A[j] <= A[i] && A[i] <= B[j]) cnt++;
best = max(best, cnt);
}
printf("%d\n", best);
}
// Sub 2: sắp xếp các sự kiện O(n log n). Cùng thời điểm thì xử lý xe đến (type 0) trước xe đi (type 1).
void sub2() {
vector<pair<int, int>> ev; // (thời điểm, loại: 0 = đến, 1 = đi)
for (int i = 0; i < n; i++) {
ev.push_back({A[i], 0});
ev.push_back({B[i], 1});
}
sort(ev.begin(), ev.end());
int cur = 0, best = 0;
for (auto &e : ev) {
if (e.second == 0) cur++;
else cur--;
best = max(best, cur);
}
printf("%d\n", best);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
cin >> n;
for (int i = 0; i < n; i++) cin >> A[i];
for (int i = 0; i < n; i++) cin >> B[i];
if (n <= 1000) sub1(); // dữ liệu nhỏ: vét cạn
else sub2();
}
return 0;
}
Bình luận