Hướng dẫn giải của [CSES 2216] Collecting Numbers
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.
Nếu số ~x~ đứng trước số ~x-1~ trong mảng, ta phải bắt đầu một lượt mới sau khi thu thập số ~x-1~.
Dựa vào nhận xét này, ta có thể kiểm tra tất cả các cặp số liên tiếp và đếm số lượt mới cần thêm. Điều này có thể thực hiện hiệu quả bằng cách lưu vị trí của mỗi số trong một mảng.
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> pos(n + 1);
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
pos[x] = i;
}
int rounds = 1;
for (int i = 2; i <= n; i++) {
if (pos[i] < pos[i - 1]) rounds++;
}
cout << rounds << "\n";
}
Chương trình tham khảo
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> pos(n + 1);
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
pos[x] = i;
}
int rounds = 1;
for (int i = 2; i <= n; i++) {
if (pos[i] < pos[i - 1]) rounds++;
}
cout << rounds << "\n";
}
Bình luận