Hướng dẫn giải của [2425 KS1] Bài 1: Kỳ thi
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