Hướng dẫn giải của [200 đề thầy Đức] Bài 22: Nhặt sỏi
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
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.
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 túi chỉ chứa một loại sỏi và tối đa k viên, nên loại i cần đúng ~\lceil w_i / k \rceil~ túi. Mỗi ngày Lý mang 2 túi, nên số ngày là ~\lceil (tổng số túi) / 2 \rceil~.
Sub 1: Đếm túi bằng mô phỏng — ~O(\sum w_i / k)~
Với mỗi loại, lặp lấy min(k, w) viên vào một túi cho đến khi hết, mỗi lần đếm thêm một túi. Đúng nhưng chậm khi k nhỏ, đạt 15/15 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long n, k;
cin >> n >> k;
long long bags = 0;
// Vét cạn: đếm từng túi. Mỗi loại sỏi lấy từng túi đầy (tối đa k viên), phần lẻ vẫn cần một túi riêng
for (int i = 0; i < n; i++) {
long long w;
cin >> w;
while (w > 0) {
w -= min(w, k);
bags++;
}
}
// Mỗi ngày mang 2 túi
cout << (bags + 1) / 2 << "\n";
return 0;
}
Sub 2: Công thức làm tròn lên — ~O(n)~
Cộng dồn ~\lceil w_i / k \rceil~ = (w_i + k - 1) / k cho mọi loại, rồi lấy ~\lceil \text{tổng} / 2 \rceil~. Đạt 15/15 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long n, k;
cin >> n >> k;
long long bags = 0;
// Loại i có w_i viên cần ceil(w_i / k) túi (mỗi túi chỉ chứa một loại)
for (int i = 0; i < n; i++) {
long long w;
cin >> w;
bags += (w + k - 1) / k;
}
// Mỗi ngày mang 2 túi nên số ngày là ceil(bags / 2)
cout << (bags + 1) / 2 << "\n";
return 0;
}
Bình luận