Hướng dẫn giải của [2425 KS1] Bài 1: Kỳ thi


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

Có hai dãy không giảm a và b, độ dài n. Mỗi thao tác chèn một số w vào a, sắp xếp lại và xóa phần tử lớn nhất. Cần số thao tác ít nhất để ai <= bi với mọi i.

Nhận xét: chèn w = 0 luôn tốt nhất, vì nó làm mọi phần tử của a không lớn hơn so với bất kỳ lựa chọn nào khác. Sau k lần chèn 0, dãy cuối cùng là k số 0 rồi đến a1..a{n-k}. Điều kiện cần kiểm tra là aj <= b{j+k} với mọi j = 1..n-k. Điều kiện này đơn điệu theo k, nên có thể tìm k nhỏ nhất bằng tìm kiếm nhị phân. Với k = n dãy toàn số 0 nên luôn thỏa mãn.

Sub 1: Mô phỏng trực tiếp — ~O(n^2 \log n)~, dùng khi ~n \le 100~

Thử k = 0, 1, 2, ...: thực hiện đúng k lần thao tác "chèn 0, sắp xếp, xóa phần tử lớn nhất", rồi kiểm tra ai <= bi. In k đầu tiên thỏa mãn.

Chấm riêng sub này: đúng 13/20 test (các test có n <= 100 đều đúng).

Sub 2: Tìm kiếm nhị phân — ~O(n \log n)~, dùng cho mọi n

Với k cho trước, kiểm tra aj <= b{j+k} với mọi j. Vì điều kiện đơn điệu theo k nên tìm k nhỏ nhất bằng nhị phân trên đoạn [0, n].

Ví dụ: n = 6, a = 10 14 20 20 22 27, b = 8 12 15 18 22 30. Với k = 1 thì a3 = 20 > b4 = 18 nên không đủ. Với k = 2: 10 <= 15, 14 <= 18, 20 <= 22, 20 <= 30 đều đúng, đáp án là 2.

Bẫy: giá trị lên tới 10^9 nên dùng long long cho an toàn khi so sánh.

Chương trình hoàn chỉnh

main đọc n, a, b (đọc từ stdin, ghi ra stdout như đề yêu cầu của máy chấm), nếu n <= 100 gọi sub1, còn lại gọi sub2.

#include <bits/stdc++.h>
using namespace std;

int n;
vector<long long> a, b;  // a[0..n-1], b[0..n-1] da sap xep khong giam

// Nhan xet: chen so w = 0 luon tot nhat (mang luon nho hon hoac bang moi cach chen khac).
// Sau k lan chen 0, mang cuoi cung la: k so 0, roi a[0..n-k-1]. Can c[i] <= b[i] voi moi i.
// Dieu kien tang theo k nen co the tim k nho nhat.

// Sub 1: mo phong truc tiep. Thu k = 0, 1, 2, ...: thuc hien k lan chen 0 (them 0, sap xep, bo phan tu lon nhat)
// roi kiem tra a[i] <= b[i]. Dung khi n <= 100.
void sub1() {
    for (int k = 0;; k++) {
        vector<long long> c = a;
        for (int t = 0; t < k; t++) {
            c.push_back(0);
            sort(c.begin(), c.end());
            c.pop_back();  // bo phan tu lon nhat
        }
        bool ok = true;
        for (int i = 0; i < n && ok; i++)
            if (c[i] > b[i]) ok = false;
        if (ok) {
            cout << k << "\n";
            return;
        }
    }
}

// Sub 2: nhi phan theo k. Voi k lan chen 0, mang cuoi la 0 (k phan tu dau) va a[0..n-k-1] tiep theo,
// nen can a[j] <= b[j+k] voi moi j = 0..n-k-1. Dieu kien don dieu theo k, tim k nho nhat bang tim kiem nhi phan. O(n log n).
bool okK(int k) {
    for (int j = 0; j + k < n; j++)
        if (a[j] > b[j + k]) return false;
    return true;
}
void sub2() {
    int lo = 0, hi = n;  // k = n luon dung (mang toan 0)
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (okK(mid)) hi = mid;
        else lo = mid + 1;
    }
    cout << lo << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    a.resize(n);
    b.resize(n);
    for (auto &x : a) cin >> x;
    for (auto &x : b) cin >> x;
    if (n <= 100) sub1();  // n nho: mo phong truc tiep
    else sub2();           // n lon: nhi phan
    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.