Hướng dẫn giải của [200 đề thầy Đức] Bài 192: Tin nhắn
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àn hình điện thoại hiển thị tối đa k cuộc hội thoại theo thứ tự từ mới đến cũ. Với mỗi tin nhắn từ người bạn d_i: nếu cuộc hội thoại với d_i đã có trên màn hình thì không thay đổi gì; nếu chưa có thì xóa cuộc hội thoại cuối cùng khi màn hình đầy, rồi đưa cuộc hội thoại với d_i lên đầu. Cần in ra danh sách cuối cùng.
Sub 1: Vét cạn bằng danh sách — ~O(N·K)~
Lưu danh sách trong vector. Mỗi tin nhắn, quét tuyến tính xem người bạn đã có trong danh sách chưa; nếu chưa và danh sách đầy thì bỏ phần tử cuối, rồi chèn người mới vào đầu. Với n, k ≤ 200 cách này đủ nhanh, đạt 21/21 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<long long> d(n);
for (auto &x : d) cin >> x;
// Vét cạn: giữ danh sách hội thoại dạng vector, mỗi lần tìm bằng quét tuyến tính
vector<long long> lst;
for (int i = 0; i < n; i++) {
bool found = false;
for (long long x : lst)
if (x == d[i]) { found = true; break; }
if (found) continue; // đã có trên màn hình: không thay đổi gì
if ((int)lst.size() == k) // đầy: xóa cuộc hội thoại cuối cùng
lst.pop_back();
lst.insert(lst.begin(), d[i]); // đưa cuộc hội thoại mới lên đầu
}
cout << lst.size() << "\n";
for (size_t i = 0; i < lst.size(); i++) {
if (i) cout << ' ';
cout << lst[i];
}
cout << "\n";
return 0;
}
Sub 2: Deque — ~O(N·K)~
Dùng deque để thêm vào đầu và bỏ ở cuối đều là thao tác O(1). Việc tìm người bạn vẫn quét O(K). Lưu ý kiểm tra trùng trước khi xử lý đầy màn hình: nếu người bạn đã có thì không bỏ gì cả. Đạt 21/21 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<long long> d(n);
for (auto &x : d) cin >> x;
// deque: thêm/xóa ở đầu và cuối đều O(1)
deque<long long> dq;
for (int i = 0; i < n; i++) {
// Nếu người bạn đã có cuộc hội thoại trên màn hình thì không làm gì
if (find(dq.begin(), dq.end(), d[i]) != dq.end()) continue;
// Màn hình đầy thì bỏ cuộc hội thoại ở cuối (vị trí k)
if ((int)dq.size() == k) dq.pop_back();
// Cuộc hội thoại mới xuất hiện ở đầu
dq.push_front(d[i]);
}
cout << dq.size() << "\n";
for (size_t i = 0; i < dq.size(); i++) {
if (i) cout << ' ';
cout << dq[i];
}
cout << "\n";
return 0;
}
Bình luận