Hướng dẫn giải của [VTT Q4 Contest 05] Bài 3: Chia kẹo [CANDY]
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
Lần lượt bỏ ~m~ viên kẹo vào hộp ít kẹo nhất (hòa thì chọn chỉ số nhỏ nhất), in số kẹo mỗi hộp. Ý chính: quá trình này "san phẳng" các hộp thấp lên cùng một mức.
Sub 1: Mô phỏng — ~O(n \cdot m)~, dùng khi ~n, m \le 5000~
Mỗi viên kẹo quét mảng tìm hộp ít kẹo nhất (so sánh chặt để giữ chỉ số nhỏ nhất) rồi tăng hộp đó thêm 1. Nếu chỉ nộp sub này: đúng 12/20 test.
Sub 2: Chặt nhị phân mức nước — ~O(n \log V)~
Tìm mức ~L~ lớn nhất sao cho chi phí nâng mọi hộp có ít hơn ~L~ viên lên đúng ~L~, tức ~\sum \max(0, L - a_i)~, không vượt quá ~m~. Hàm chi phí tăng theo ~L~ nên chặt nhị phân được (~L~ tối đa khoảng ~2 \cdot 10^9~, dùng long long). Sau khi nâng, còn dư ~r~ viên với ~r~ nhỏ hơn số hộp đang có đúng ~L~ viên (vì mức ~L+1~ không đủ kẹo). Những viên dư này lần lượt rơi vào các hộp có ~L~ viên theo thứ tự chỉ số tăng dần, nên chỉ cần duyệt từ trái sang phải cộng thêm 1 cho ~r~ hộp đầu tiên có ~L~ viên. 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, nếu ~n \le 5000~ và ~m \le 5000~ 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;
long long m;
long long a[100005];
// Sub 1: mô phỏng từng viên kẹo, mỗi lần tìm hộp ít kẹo nhất — O(n*m)
void sub1() {
for (long long k = 0; k < m; k++) {
int p = 0;
for (int i = 1; i < n; i++)
if (a[i] < a[p]) p = i; // dùng < nên giữ chỉ số nhỏ nhất khi bằng nhau
a[p]++;
}
for (int i = 0; i < n; i++) cout << a[i] << " ";
cout << "\n";
}
// Sub 2: chặt nhị phân mức L lớn nhất sao cho nâng mọi hộp lên ít nhất L tốn <= m viên
void sub2() {
long long lo = 0, hi = 2000000000LL;
while (lo < hi) {
long long mid = (lo + hi + 1) / 2;
long long cost = 0;
for (int i = 0; i < n; i++)
if (a[i] < mid) cost += mid - a[i];
if (cost <= m) lo = mid;
else hi = mid - 1;
}
long long L = lo, cost = 0;
for (int i = 0; i < n; i++)
if (a[i] < L) { cost += L - a[i]; a[i] = L; }
long long r = m - cost; // còn dư r viên, r < số hộp đang có L kẹo
for (int i = 0; i < n && r > 0; i++)
if (a[i] == L) { a[i]++; r--; }
for (int i = 0; i < n; i++) cout << a[i] << " ";
cout << "\n";
}
int main() {
freopen("CANDY.INP", "r", stdin);
freopen("CANDY.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> m;
for (int i = 0; i < n; i++) cin >> a[i];
if (n <= 5000 && m <= 5000) sub1();
else sub2();
}
Bình luận