Hướng dẫn giải của [200 đề thầy Đức] Bài 43: Ông già Noel chia kẹo
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ô phỏng đúng quy trình: người đầu hàng nhận m chiếc kẹo; nếu chưa đủ thì quay lại cuối hàng, nếu đủ thì ra khỏi hàng. Người ra khỏi hàng cuối cùng là đáp án.
Sub 1: Mô phỏng với vector — ~O(S \cdot N)~
Lưu hàng bằng vector. Mỗi lần lấy người đầu hàng bằng erase (dịch cả mảng), rồi thêm vào cuối nếu chưa đủ kẹo. Đúng nhưng mỗi bước tốn O(N). Đạt 49/49 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<int> a(n), got(n, 0);
for (int i = 0; i < n; i++) cin >> a[i];
// Hang duoc luu bang vector: chi so hoc sinh theo thu tu xep hang
vector<int> hang(n);
for (int i = 0; i < n; i++) hang[i] = i;
int last = -1;
while (!hang.empty()) {
int i = hang[0];
hang.erase(hang.begin()); // em dau hang nhan m keo
got[i] += m;
if (got[i] < a[i]) hang.push_back(i); // chua du thi ve cuoi hang
else last = i + 1; // du roi thi ra khoi hang
}
cout << last << "\n";
return 0;
}
Sub 2: Mô phỏng với hàng đợi (deque) — ~O(S)~
Dùng deque để lấy đầu hàng và thêm cuối hàng đều O(1). Tổng số bước không vượt quá tổng số kẹo chia cho m cộng N, nên rất nhanh. Đạt 49/49 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<int> a(n), got(n, 0);
for (int i = 0; i < n; i++) cin >> a[i];
// Hang doi FIFO: deque cho phep lay dau hang va them cuoi hang trong O(1)
deque<int> hang;
for (int i = 0; i < n; i++) hang.push_back(i);
int last = -1;
while (!hang.empty()) {
int i = hang.front();
hang.pop_front();
got[i] += m;
if (got[i] < a[i]) hang.push_back(i); // chua du keo thi ve cuoi hang
else last = i + 1; // du keo thi ra khoi hang
}
cout << last << "\n";
return 0;
}
Bình luận