Hướng dẫn giải của [VT Thiếu nhi] BÀI 27: HELP
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
Robin duyệt lần lượt từng người, giữ số vàng đang có. Người có ai ≥ k thì Robin lấy hết vàng; người có ai = 0 và Robin còn vàng thì Robin cho 1 vàng và đếm thêm 1.
Sub 1: Mô phỏng lại từ đầu cho mỗi người — ~O(n^2)~
Với mỗi người i, tính lại số vàng Robin có từ đầu bằng cách duyệt các người 1..i-1, rồi kiểm tra người i có được cho vàng không. Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
if (fopen("HELP.INP", "r")) { freopen("HELP.INP", "r", stdin); freopen("HELP.OUT", "w", stdout); }
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
vector<long long> a(n);
for (auto &x : a) cin >> x;
// Vét cạn: với mỗi người i, mô phỏng lại từ đầu các người 1..i-1 để biết Robin còn bao nhiêu vàng
int cnt = 0;
for (int i = 0; i < n; i++) {
long long coin = 0;
for (int j = 0; j < i; j++) {
if (a[j] >= k) coin += a[j]; // lấy hết vàng
else if (a[j] == 0 && coin > 0) { coin--; } // cho 1 vàng
}
if (a[i] == 0 && coin > 0) cnt++; // người i được cho vàng
}
cout << cnt << "\n";
}
return 0;
}
Sub 2: Duyệt một lượt, giữ số vàng — ~O(n)~
Duyệt một lần và cập nhật trực tiếp số vàng và bộ đếm. Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
if (fopen("HELP.INP", "r")) { freopen("HELP.INP", "r", stdin); freopen("HELP.OUT", "w", stdout); }
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
long long coin = 0; // số vàng Robin đang có
int cnt = 0; // số người Robin cho vàng
for (int i = 0; i < n; i++) {
long long a;
cin >> a;
if (a >= k) {
coin += a; // lấy hết vàng của người này
} else if (a == 0 && coin > 0) {
coin--; // cho người nghèo 1 vàng
cnt++;
}
}
cout << cnt << "\n";
}
return 0;
}
Bình luận