Hướng dẫn giải của Đầu bếp
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 đầu bếp chỉ làm một dĩa, bánh bèo (giá trị ~a_i~) hoặc bánh lọc (giá trị ~b_i~). Với mỗi ~k~, cần chọn đúng ~k~ đầu bếp làm bánh bèo sao cho tổng độ ngon lớn nhất.
Sub 1: Vét cạn theo tập con — ~O(2^N \cdot N)~, dùng khi ~N \le 20~
Duyệt mọi tập con các đầu bếp làm bánh bèo (2^N cách). Với tập có ~k~ phần tử, cập nhật ~t_k~ bằng tổng lớn nhất.
Nếu chỉ nộp sub này: đúng 5/20 test.
Sub 2: Sắp xếp theo hiệu — ~O(N \log N)~
Đặt ~d_i = a_i - b_i~. Tổng khi chọn tập ~S~ làm bánh bèo là ~\sum b_i + \sum_{i \in S} d_i~. Với ~k~ cố định, chọn ~k~ giá trị ~d_i~ lớn nhất. Sắp ~d~ giảm dần và cộng dồn: ~t_k = \sum b_i + (d_1 + ... + d_k)~.
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Hàm main đọc dữ liệu rồi chọn sub theo kích thước: dữ liệu nhỏ gọi sub 1 (vét cạn), dữ liệu lớn gọi sub cuối. Khi đi thi, nên nộp đầy đủ như vậy: nếu sub sau sai hoặc chưa kịp làm thì vẫn ăn điểm các sub trước.
#include <bits/stdc++.h>
using namespace std;
int N;
vector<long long> a, b; // a: độ ngon bánh bèo, b: độ ngon bánh lọc
// Sub 1: vét cạn — mỗi đầu bếp chọn bánh bèo (bit 1) hoặc bánh lọc (bit 0): 2^N cách.
// Cách có k bit 1 cho tổng ở t_k. O(2^N * N), dùng khi N <= 20
void sub1() {
vector<long long> best(N + 1, LLONG_MIN);
for (int mask = 0; mask < (1 << N); mask++) {
long long sum = 0;
int k = 0;
for (int i = 0; i < N; i++) {
if (mask >> i & 1) { sum += a[i]; k++; }
else sum += b[i];
}
best[k] = max(best[k], sum);
}
for (int k = 1; k <= N; k++) cout << best[k] << (k == N ? "\n" : " ");
}
// Sub 2: đầu bếp i chọn bánh bèo thì hơn chọn bánh lọc một lượng d_i = a_i - b_i.
// Nên t_k = (tổng b_i) + (tổng k số d_i lớn nhất). Sắp d giảm dần rồi cộng dồn. O(N log N)
void sub2() {
long long sumB = 0;
vector<long long> d(N);
for (int i = 0; i < N; i++) { sumB += b[i]; d[i] = a[i] - b[i]; }
sort(d.rbegin(), d.rend());
long long cur = sumB;
for (int k = 1; k <= N; k++) {
cur += d[k - 1];
cout << cur << (k == N ? "\n" : " ");
}
}
int main() {
freopen("CHEF.INP", "r", stdin);
freopen("CHEF.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> N;
a.resize(N); b.resize(N);
for (int i = 0; i < N; i++) cin >> a[i];
for (int i = 0; i < N; i++) cin >> b[i];
if (N <= 20) sub1(); // dữ liệu nhỏ: vét cạn
else sub2();
return 0;
}
Bình luận