CTDL và giải thuật - Bài tập hay về hàng đợi
Huyền có một cái điện thoại, màn hình điện thoại của Huyền chỉ hiển thị được tối đa k
tin nhắn. Màn hình của Huyền hiện thị như sau:
- Không hiện thị
2
tin nhắn của cùng một số điện thoại (SĐT) trên cùng một khung hình, nếu SĐT a gửi tin nhắn đến mà trên màn hình đã có tin nhắn của SĐT a thì màn hình không thay đổi gì. - Khi SĐT
a
gửi tin nhắn đến mà trên màn hình chưa có tin nhắn của SĐT a thì:- Nếu màn hình chưa đủ
k
tin nhắn thì tin nhắn của SĐTa
sẽ được chèn vào cuối màn hình. - Nếu màn hình đã có đủ
k
tin nhắn thì thì màn hình sẽ đẩy tin nhắn trên cùng ra và sau đó chèn tin nhắn của SĐTa
vào cuối màn hình.
- Nếu màn hình chưa đủ
Cho dãy a
là các SĐT sẽ gửi tin nhắn cho Huyền. Hỏi sau khi nhận được tin nhắn cuối cùng thì màn hình của Huyền đang hiển thì tin nhắn của các SĐT nào, đưa ra theo thứ tự từ trên xuống dưới của màn hình.
Ví dụ:
- Test mẫu 1:
Input Output 5
1 2 1 3 4
32 3 4
Vớia = [1, 2, 1, 3, 4]
,k = 3
. thìmessagesPhone(a) = [2, 3, 4]
;
Giải thích:- Lúc đầu màn hình điện thoại rỗng
[]
. - Sau khi
1
nhắn tin đến thì màn hình hiển thì[1]
. - Sau khi
2
nhắn tin đến thì màn hình hiển thị[1, 2]
. - Sau khi
1
nhắn tin đến thì màn hình không thay đổi gì vì trên màn hình đã có tin nhắn của1
rồi. - Sau khi
3
nhắn tin đến màn hình hiển thị[1, 2, 3]
- Sau khi
4
nhắn tin đến, lúc này màn hình đã hiển thị đủ3
tin nhắn rồi nên điện thoại sẽ đẩy tin nhắn đầu tiên là1
đi và chèn tin nhắn của4
vào cuối, cuối cùng màn hình hiển thị[2, 3, 4]
.
- Lúc đầu màn hình điện thoại rỗng
Hướng dẫn bài tập.
Dùng một queue để lưu những số (tin nhắn) theo thứ tự nhắn đến.
Dùng một vector để đánh dấu sự xuất hiện của các số trong queue.
Nếu một số chưa xuất hiện trong queue thì thêm vào queue nhưng phải đảm bảo rằng số phần tử trong queue phải nhỏ hơn hoặc bằng k
.
Code mẫu:
Ngôn ngữ C++:
#include<iostream>
#include<queue>
using namespace std;
int main(){
queue<int> q;
bool b[1001];
int a[1001];
int n, k;
cin >>n;
for (int i = 0; i < 1001; i++){
b[i] = false;
}
for (int i = 0; i < n; i++){
cin >> a[i];
}
cin >> k;
for (int i = 0; i < n; i++)
if (!b[a[i]]){
if (q.size() < k){
b[a[i]] = true;
q.push(a[i]);
}
else{
b[q.front()] = false;
b[a[i]] = true;
q.push(a[i]);
q.pop();
}
}
while (!q.empty()){
cout << q.front() << " ";
q.pop();
}
return 0;
}