Hướng dẫn giải của [VTT Q4 Contest 03] Bài 2: Bánh sinh nhật [CAKES]
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 chồng có tối đa 2 bánh, nên số chồng bằng ~n~ trừ đi số cặp ghép được. Ta cần ghép được nhiều cặp nhất, trong đó bánh trên nhẹ bằng nhiều nhất nửa bánh dưới.
Sub 1: Thử từng số cặp — ~O(n^2)~, dùng khi ~n \le 1000~
Sắp xếp tăng dần. Nếu ghép được ~k~ cặp thì luôn có thể chọn ~k~ bánh nhẹ nhất làm bánh trên và ~k~ bánh nặng nhất làm bánh dưới, bánh nhẹ thứ ~i~ ghép với bánh nặng thứ ~i~ trong nhóm nặng. Với mỗi ~k~ ta kiểm tra điều kiện trong ~O(k)~, lấy ~k~ lớn nhất thỏa mãn. Nếu chỉ nộp sub này: đúng 13/20 test.
Sub 2: Hai con trỏ — ~O(n \log n)~
Tách hẳn nửa nhẹ (~n/2~ bánh nhỏ nhất) làm bánh trên, con trỏ ~j~ chạy trên nửa nặng. Với từng bánh nhẹ theo thứ tự tăng dần, đẩy ~j~ tới bánh đầu tiên có trọng lượng ít nhất gấp đôi, ghép rồi chuyển ~j~ sang bánh kế. Chú ý nhân đôi bằng long long và chỉ lấy tối đa ~n/2~ cặp. Đúng 20/20 test.
Chương trình hoàn chỉnh
Main đọc dữ liệu; nếu ~n \le 1000~ gọi sub1, ngược lại gọi sub2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
int n;
vector<long long> a;
// Sub 1: thử từng số cặp k: k bánh nhẹ nhất đặt lên k bánh nặng nhất (nhẹ thứ i ghép nặng thứ i) — O(n^2)
void sub1() {
sort(a.begin(), a.end());
int pairs = 0;
for (int k = 1; 2 * k <= n; k++) {
bool ok = true;
for (int i = 0; i < k && ok; i++)
if (a[n - k + i] < 2 * a[i]) ok = false;
if (ok) pairs = k;
}
cout << n - pairs << "\n";
}
// Sub 2: cũng tham lam nhưng dùng hai con trỏ — O(n log n) do sắp xếp
void sub2() {
sort(a.begin(), a.end());
int pairs = 0;
int j = n / 2; // các bánh dưới chỉ lấy từ nửa lớn
for (int i = 0; i < n / 2 && j < n; i++) {
while (j < n && a[j] < 2 * a[i]) j++;
if (j < n) { pairs++; j++; }
}
cout << n - pairs << "\n";
}
int main() {
freopen("CAKES.INP", "r", stdin);
freopen("CAKES.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
a.resize(n);
for (auto &x : a) cin >> x;
if (n <= 1000) sub1();
else sub2();
}
Bình luận