Hướng dẫn giải của [200 đề thầy Đức] Bài 83: Mua kem nhận quà
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
Có $n$ hộp kem, trong đó đúng $s$ hộp có nhãn dán và đúng $t$ hộp có đồ chơi (một hộp có thể có cả hai). Mỗi hộp đều có ít nhất một thứ, vì $s + t \ge n$. Vova không biết hộp nào có gì và phải mua một số hộp để chắc chắn được ít nhất một nhãn dán và một đồ chơi. Tìm số hộp ít nhất phải mua.
Sub 1: Vét cạn từng hộp — ~O(n)~
Duyệt qua $n$ hộp (đánh dấu hộp $i$ có nhãn dán nếu $i < s$, có đồ chơi nếu $i \ge n - t$), đếm số hộp không có nhãn dán và số hộp không có đồ chơi. Đáp án là số lớn hơn trong hai số đó cộng 1. Cách này đúng nhưng chậm khi $n$ lớn (đạt 3/21 test, 18 test quá giờ, không sai test nào).
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
vector<array<long long, 3>> qs(T);
for (auto &q : qs) cin >> q[0] >> q[1] >> q[2]; // n, s, t
for (auto &q : qs) {
long long n = q[0], s = q[1], t = q[2];
// Vét cạn từng hộp: hộp thứ i có nhãn dán nếu i < s, có đồ chơi nếu i >= n - t
// (mỗi hộp có ít nhất một thứ vì s + t >= n). Đếm số hộp không có nhãn dán và
// số hộp không có đồ chơi.
long long noSticker = 0, noToy = 0;
for (long long i = 0; i < n; i++) {
if (!(i < s)) noSticker++;
if (!(i >= n - t)) noToy++;
}
// Nếu mua k hộp mà k > số hộp thiếu nhãn (hoặc thiếu đồ chơi) thì chắc chắn có đủ.
// Trường hợp xấu nhất: mua toàn bộ hộp thiếu một loại, nên đáp án là max + 1.
cout << max(noSticker, noToy) + 1 << "\n";
}
return 0;
}
Sub 2: Công thức đếm hộp thiếu — ~O(1)~
Số hộp không có nhãn dán là $n - s$ (đó là các hộp chỉ có đồ chơi). Số hộp không có đồ chơi là $n - t$ (các hộp chỉ có nhãn dán).
Trường hợp xấu nhất là Vova mua toàn bộ các hộp thiếu một loại. Mua một số hộp lớn hơn số hộp thiếu nhãn dán và lớn hơn số hộp thiếu đồ chơi là đủ, nên đáp án là $\max(n-s,\ n-t) + 1$.
Ví dụ $n = 10$, $s = 5$, $t = 7$: $\max(5, 3) + 1 = 6$. Ví dụ $10\ 10\ 10$: $\max(0, 0) + 1 = 1$. Ví dụ $2\ 1\ 1$: $\max(1, 1) + 1 = 2$.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
long long n, s, t;
cin >> n >> s >> t;
// Có n - s hộp không có nhãn dán (toàn đồ chơi) và n - t hộp không có đồ chơi (toàn nhãn dán).
// Trường hợp xấu nhất là Vova mua toàn bộ các hộp thiếu một loại, nên số hộp cần mua
// là max(n - s, n - t) + 1 để chắc chắn có cả nhãn dán và đồ chơi.
// Ví dụ: n = 10, s = 5, t = 7 -> max(5, 3) + 1 = 6.
cout << max(n - s, n - t) + 1 << "\n";
}
return 0;
}
Bình luận