Hướng dẫn giải của [200 đề thầy Đức] Bài 190: Hình vuông lớn nhất
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 tấm ván chỉ lấy được tối đa một đoạn. Để có mặt bàn vuông cạnh ~s~ cần ~s~ đoạn dài ít nhất ~s~, lấy từ ~s~ tấm khác nhau. Đáp án là ~s~ lớn nhất thỏa điều kiện: số tấm có ~a_i \ge s~ không nhỏ hơn ~s~.
Sub 1: Vét cạn — ~O(n^2)~, dùng khi ~n \le 100~
Thử mọi cạnh ~s = 1, \dots, n~, với mỗi ~s~ đếm số tấm có ~a_i \ge s~, lấy ~s~ lớn nhất thỏa điều kiện.
Sub 2: Tìm nhị phân — ~O(n \log n)~
Điều kiện "số tấm có ~a_i \ge s~ không nhỏ hơn ~s~" đơn điệu: ~s~ càng lớn càng khó thỏa. Tìm ~s~ lớn nhất bằng tìm nhị phân, mỗi lần kiểm tra ~O(n)~.
Chương trình hoàn chỉnh
main đọc ~q~ truy vấn. Với mỗi truy vấn, nếu ~n \le 100~ thì gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int n;
long long a[1005]; // độ dài các tấm ván
// Mỗi tấm ván chỉ lấy được tối đa một đoạn (cắt đúng độ dài s từ đầu tấm).
// Muốn mặt vuông cạnh s cần s đoạn dài ít nhất s, nên: đếm số tấm có a[i] >= s và so với s.
bool ok(int s) {
long long cnt = 0;
for (int i = 1; i <= n; i++)
if (a[i] >= s) cnt++;
return cnt >= s;
}
// Sub 1: vét cạn O(n^2). Thử mọi cạnh s từ 1 đến n, lấy s lớn nhất thỏa mãn.
void sub1() {
int best = 1;
for (int s = 1; s <= n; s++)
if (ok(s)) best = max(best, s);
printf("%d\n", best);
}
// Sub 2: O(n log n). ok(s) đơn điệu (s càng lớn càng khó thỏa), nên tìm s lớn nhất bằng tìm nhị phân.
void sub2() {
int lo = 1, hi = n;
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
if (ok(mid)) lo = mid;
else hi = mid - 1;
}
printf("%d\n", lo);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> q;
while (q--) {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
if (n <= 100) sub1(); // dữ liệu nhỏ: vét cạn
else sub2();
}
return 0;
}
Bình luận