Hướng dẫn giải của [CSES 1141] Playlist
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.
Chúng ta duyệt qua danh sách các bài hát và tính độ dài của đoạn dài nhất kết thúc tại mỗi vị trí.
Vì ta muốn mọi bài hát trong đoạn đều là duy nhất, ta cũng lưu vị trí cuối cùng đã thấy mỗi bài hát. Sử dụng thông tin này, ta có thể duy trì biên trái của đoạn.
#include <iostream>
#include <map>
using namespace std;
int main() {
int n;
cin >> n;
map<int, int> last;
int left = 0;
int best = 0;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
left = max(left, last[x]);
best = max(best, i - left);
last[x] = i;
}
cout << best << "\n";
}
Chương trình tham khảo
#include <iostream>
#include <map>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
map<int, int> last;
int left = 0;
int best = 0;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
left = max(left, last[x]);
best = max(best, i - left);
last[x] = i;
}
cout << best << "\n";
}
Bình luận