Hướng dẫn giải của [Beginner Free Contest 06] POTTERY
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
Ngày làm việc dài ~T~ chỉ có đúng một lần chuyển hàng từ phân xưởng nặn sang phân xưởng vẽ. Vậy phân xưởng nặn làm trong ~t~ đơn vị đầu, phân xưởng vẽ làm trong ~T-t~ đơn vị còn lại. Trong ~t~ đơn vị thời gian, các thợ nặn làm được ~\sum \lfloor t/a_i \rfloor~ sản phẩm, các thợ vẽ trong ~T-t~ làm được ~\sum \lfloor (T-t)/b_j \rfloor~ sản phẩm; số sản phẩm hoàn chỉnh là giá trị nhỏ hơn của hai số này. Cần chọn ~t~ để tối đa hóa.
Sub 1: Thử mọi ~t~ — ~O(T \cdot (N+M))~, dùng khi ~T \le 1000, N, M \le 100~
Duyệt ~t = 0..T~, tính hai tổng và lấy ~\min~, giữ giá trị lớn nhất. Nếu chỉ nộp sub này: đúng 10/20 test.
Sub 2: Chặt nhị phân — ~O((N+M) \log T)~
Số sản phẩm nặn tăng theo ~t~, số sản phẩm vẽ giảm theo ~t~. Tìm ~t~ nhỏ nhất để nặn ~\ge~ vẽ bằng chặt nhị phân; đáp án là max của giá trị ~\min~ tại ~t~ và tại ~t-1~ (hai bên điểm cắt). Tổng có thể lớn tới ~10^{14}~ nên dùng ~long long~. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Main đọc ~T~, dãy ~a~, dãy ~b~ (máy chấm dùng đọc/ghi chuẩn); dữ liệu nhỏ gọi sub1, lớn 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;
long long T;
int n, m;
vector<long long> a, b;
// Số sản phẩm nặn được trong t đơn vị thời gian (mỗi thợ nặn liên tục) và số sản phẩm vẽ được
long long molded(long long t) { long long s = 0; for (long long x : a) s += t / x; return s; }
long long painted(long long t) { long long s = 0; for (long long x : b) s += t / x; return s; }
// Sub 1: thử mọi thời điểm chuyển hàng t = 0..T. Phân xưởng nặn làm trong t, vẽ làm trong T - t.
// Số sản phẩm = min(nặn, vẽ). Dùng khi T <= 1000, n, m <= 100.
void sub1() {
long long best = 0;
for (long long t = 0; t <= T; t++) best = max(best, min(molded(t), painted(T - t)));
printf("%lld\n", best);
}
// Sub 2: molded(t) tăng, painted(T-t) giảm theo t -> chặt nhị phân t nhỏ nhất để molded >= painted,
// đáp án là max của min tại t và t-1. O((n+m) log T)
void sub2() {
long long lo = 0, hi = T; // t = T luôn thỏa vì painted(0) = 0
while (lo < hi) {
long long mid = (lo + hi) / 2;
if (molded(mid) >= painted(T - mid)) hi = mid; else lo = mid + 1;
}
long long best = min(molded(lo), painted(T - lo));
if (lo > 0) best = max(best, min(molded(lo - 1), painted(T - lo + 1)));
printf("%lld\n", best);
}
int main() {
scanf("%lld %d", &T, &n);
a.resize(n);
for (auto &x : a) scanf("%lld", &x);
scanf("%d", &m);
b.resize(m);
for (auto &x : b) scanf("%lld", &x);
if (T <= 1000 && n <= 100 && m <= 100) sub1();
else sub2();
return 0;
}
Bình luận