Hướng dẫn giải của [200 đề thầy Đức] Bài 170: Số điểm đỗ tối thiểu


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.

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

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.