Hướng dẫn giải của [TKNP] FGIFT
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 bạn nữ chỉ nhận một loại hoa. Nếu loại i có ai bông và chia cho gi bạn nữ thì bạn nhận nhiều nhất \lceil ai / gi \rceil bông. Muốn số hoa nhiều nhất của một bạn là X thì loại i cần đúng \lceil ai / X \rceil bạn nữ, và tổng số bạn cần dùng là \sum \lceil ai / X \rceil phải không vượt quá N.
Do đó đáp án là X nhỏ nhất sao cho \sum \lceil a_i / X \rceil \le N. Hàm này đơn điệu theo X nên có thể tìm X bằng vét cạn hoặc nhị phân. Vì M \le N, X = max(a) luôn thỏa mãn.
Sub 1: Vét cạn theo X — ~O(\max(a) \cdot M)~, dùng khi \max(a) \cdot M \le 10^7
Thử lần lượt X = 1, 2, ..., max(a), dừng ở X đầu tiên thỏa \sum \lceil a_i / X \rceil \le N. Nếu chỉ nộp sub này: đúng 3/8 test (5 test còn lại có a lớn, chạy quá giờ).
Sub 2 (đầy đủ): Tìm nhị phân trên X — ~O(M \log(\max(a)))~
Tìm nhị phân X trong đoạn [1, max(a)] với điều kiện trên.
Bẫy: \sum \lceil a_i / X \rceil có thể lên tới khoảng 3 \cdot 10^{14} khi M \cdot 10^9, dùng long long. Công thức \lceil a / X \rceil viết là (a + X - 1) / X.
Nếu chỉ nộp sub này: đúng 8/8 test.
Chương trình hoàn chỉnh
Hàm main đọc N, M và các a_i. Nếu max(a) \cdot M \le 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.
#include <bits/stdc++.h>
using namespace std;
long long N; // so ban nu
int M; // so loai hoa
vector<long long> a; // a[i]: so bong hoa loai i
// Voi moi ban nu nhan toi da X bong, loai hoa i can g_i = ceil(a_i / X) ban nu.
// Dap an X kha thi khi tong g_i <= N.
bool feasible(long long X) {
long long need = 0;
for (int i = 0; i < M; i++) need += (a[i] + X - 1) / X;
return need <= N;
}
// Sub 1: vet can - thu lan luot X = 1, 2, ... cho den khi kha thi. Dung khi max(a) * M <= 10^7.
void sub1() {
long long mx = *max_element(a.begin(), a.end());
for (long long X = 1; X <= mx; X++)
if (feasible(X)) {
cout << X << "\n";
return;
}
}
// Sub 2: day du - tim nhi phan X nho nhat kha thi, X nam trong [1, max(a)].
void sub2() {
long long lo = 1, hi = *max_element(a.begin(), a.end());
while (lo < hi) {
long long mid = (lo + hi) / 2;
if (feasible(mid)) hi = mid;
else lo = mid + 1;
}
cout << lo << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> M;
a.resize(M);
for (int i = 0; i < M; i++) cin >> a[i];
long long mx = *max_element(a.begin(), a.end());
if (mx * M <= 10000000LL) sub1(); // du lieu nho: vet can
else sub2();
return 0;
}
Bình luận