Hướng dẫn giải của Xếp gạch
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 lượt có thể bỏ qua, hoặc xếp ~b_i~ viên lên chồng ~j~ nếu các chồng ~j, j+1, \dots, n~ chưa từng được xếp thêm. Điều đó có nghĩa là các chồng được xếp thêm phải có chỉ số tăng dần theo thời gian, mỗi chồng được xếp thêm tối đa một lần. Cần cực đại hóa số gạch của chồng ít nhất.
Sub 1: Vét cạn — dùng khi ~m \le 2~ và ~n^{m+1}~ nhỏ
Thử mọi cách: mỗi lượt bỏ qua hoặc chọn chồng ~j~ lớn hơn chồng đã chọn ở lượt trước, cuối cùng lấy min các chồng. Với ~m = 1~ là ~O(n^2)~, với ~m = 2~ là ~O(n^3)~. Nếu chỉ nộp sub này: đúng 8/20 test.
Sub 2: Chặt nhị phân + tham lam — ~O((n+m) \log A)~
Chặt nhị phân điểm số ~X~. Chồng có ~a_i \ge X~ không cần xếp thêm; chồng có ~a_i < X~ cần một giá trị ~b \ge X - a_i~. Do thứ tự chồng tăng dần theo thứ tự lượt, ta duyệt các chồng từ trái sang phải với con trỏ ~p~ trên dãy ~b~: với chồng cần ~need~, tiến ~p~ đến lượt đầu tiên có ~b_p \ge need~ rồi dùng nó (dùng càng sớm càng để lại nhiều lượt cho các chồng sau). Nếu hết lượt thì ~X~ không đạt được. Đáp án tối đa cỡ ~2 \cdot 10^8~. Nếu chỉ nộp sub này: đúng 20/20 test. Lưu ý dữ liệu thật có ~n, m~ lớn hơn 10^5 nên mảng cần đủ lớn.
Chương trình hoàn chỉnh
Hàm main đọc dữ liệu (đọc/ghi file B3.INP/B3.OUT); nếu ~m \le 2~ và ~n^{m+1} \le 5 \cdot 10^7~ 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. Kết quả: 20/20 test.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m;
ll a[2000005], b[2000005], cur[2000005];
ll best;
// Sub 1: thử mọi cách: mỗi lượt bỏ qua hoặc xếp vào chồng j lớn hơn mọi chồng đã xếp trước đó.
// Dùng khi n^m * n nhỏ (m = 1 hoặc 2 và n nhỏ).
void dfs(int turn, int last) {
if (turn == m || last == n) {
ll mn = LLONG_MAX;
for (int i = 1; i <= n; i++) mn = min(mn, cur[i]);
best = max(best, mn);
return;
}
dfs(turn + 1, last); // bỏ qua lượt này
for (int j = last + 1; j <= n; j++) { // xếp vào chồng j
cur[j] += b[turn + 1];
dfs(turn + 1, j);
cur[j] -= b[turn + 1];
}
}
void sub1() {
for (int i = 1; i <= n; i++) cur[i] = a[i];
best = 0;
dfs(0, 0);
cout << best << "\n";
}
// Sub 2: chặt nhị phân đáp án X, kiểm tra tham lam O(n + m)
// Các chồng được xếp theo thứ tự tăng dần của vị trí và lượt, mỗi chồng nhận tối đa một giá trị b.
bool ok(ll X) {
int p = 1; // lượt b tiếp theo có thể dùng
for (int i = 1; i <= n; i++) {
if (a[i] >= X) continue;
ll need = X - a[i];
while (p <= m && b[p] < need) p++;
if (p > m) return false;
p++;
}
return true;
}
void sub2() {
ll lo = 0, hi = 300000000LL;
while (lo < hi) {
ll mid = (lo + hi + 1) / 2;
if (ok(mid)) lo = mid; else hi = mid - 1;
}
cout << lo << "\n";
}
int main() {
freopen("B3.INP", "r", stdin);
freopen("B3.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= m; i++) cin >> b[i];
double work = n;
for (int i = 0; i < m && work < 1e18; i++) work *= n;
if (m <= 2 && work <= 5e7) sub1();
else sub2();
return 0;
}
Bình luận