Hướng dẫn giải của Pho_to
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.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
, , ,
Hiểu bài toán
Bài toán mô phỏng việc di chuyển các vận động viên (VĐV) trong một hàng dọc theo các giao dịch (transactions). Ban đầu, các VĐV được xếp theo thứ tự từ 1 đến n. Mỗi giao dịch gồm hai số i và j, yêu cầu di chuyển VĐV i đến vị trí ngay bên trái của VĐV j. Nếu j = 0, VĐV i được chuyển đến cuối hàng. Chúng ta cần mô phỏng chính xác quá trình này sau m giao dịch và xuất ra vị trí cuối cùng của từng VĐV.
Các cách tiếp cận
Cách Mô phỏng bằng Danh sách liên kết kép (Double Linked List)
#include <iostream>
#include <vector>
using namespace std;
int main() {
// Tối ưu hóa tốc độ nhập xuất
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// Đọc từ file input và ghi ra file output
if (fopen("photo.inp", "r")) {
freopen("photo.inp", "r", stdin);
freopen("photo.out", "w", stdout);
}
int n, m;
if (!(cin >> n >> m)) return 0;
// Dùng mảng tĩnh thay vì vector cho tốc độ nhanh hơn
// left[i]: VĐV ở ngay bên trái i
// right[i]: VĐV ở ngay bên phải i
// left[i] = 0 hoặc right[i] = 0 nghĩa là không có ai (đầu hoặc cuối hàng)
vector<int> left(n + 1);
vector<int> right(n + 1);
// Khởi tạo hàng ban đầu: 1 <-> 2 <-> ... <-> n
for (int i = 1; i <= n; ++i) {
left[i] = i - 1;
right[i] = i + 1;
}
// Điều chỉnh ranh giới
left[1] = 0; // 1 là đầu hàng
right[n] = 0; // n là cuối hàng
// Xử lý m giao dịch
for (int k = 0; k < m; ++k) {
int i, j;
cin >> i >> j;
// Bước 1: Loại bỏ VĐV i khỏi vị trí hiện tại
// Nếu i đang ở đầu hoặc cuối, giá trị 0 sẽ không gây lỗi
int l = left[i]; // VĐV bên trái i cũ
int r = right[i]; // VĐV bên phải i cũ
if (l != 0) right[l] = r; // Cập nhật người bên phải của l
if (r != 0) left[r] = l; // Cập nhật người bên trái của r
// Bước 2: Chèn VĐV i vào bên trái j
// Nếu j = 0, chèn vào cuối hàng (tương đương bên trái "vô hình")
// Nếu j = 0, left[j] mặc định là 0, ta cần tìm phần tử cuối thực sự
// Tuy nhiên, logic chèn vào trước j:
// left[j] sẽ là l mới của i
// i sẽ là left mới của j
// Nếu j = 0, ta cần xử lý đặc biệt: đưa i vào cuối
if (j == 0) {
// Tìm phần tử cuối cùng hiện tại
int last = 0;
// Có thể tối ưu bằng cách lưu tail nếu muốn, nhưng với n nhỏ thì tìm từ đầu cũng được
// Hoặc đơn giản là chèn vào sau phần tử cuối cùng trong hàng
// Logic chèn vào trước j=0 là chèn vào cuối:
// left[i] = last_element_of_list
// right[last_element_of_list] = i
// right[i] = 0
// Biến pháp: Nếu j=0, ta coi như chèn vào sau phần tử cuối cùng của hàng
// Ta cần trỏ left[i] vào phần tử cuối cùng
// Biến pháp khác: Dùng dummy node hoặc sentinel
// Code dưới đây xử lý j != 0 và j = 0 một cách tổng quát:
// Nếu j=0, ta cần chèn vào cuối.
// Ta có thể dùng biến 'tail' lưu phần tử cuối.
// Nếu không, ta phải duyệt (O(n)) -> không tối ưu.
// Tối ưu O(1): Dùng sentinel node hoặc biến lưu tail.
// Giả sử ta dùng biến tail để lưu phần tử cuối.
// Tuy nhiên, code template thường chỉ dùng mảng left/right.
// Biến pháp: Nếu j=0, ta chèn i vào sau phần tử cuối cùng.
// Nhưng làm sao biết phần tử cuối cùng?
// Nếu ta dùng dummy node 0 và n+1:
// left[0] là tail? Không.
// Ta thêm node 0 làm đầu giả, node n+1 làm cuối giả.
}
// Để xử lý j=0 hiệu quả O(1), ta thêm 2 node giả:
// Node 0: Head giả (luôn đứng đầu)
// Node n+1: Tail giả (luôn đứng cuối)
// Ban đầu: 0 <-> 1 <-> 2 ... <-> n <-> (n+1)
}
// Code hoàn chỉnh với Sentinel:
vector<int> L(n + 2), R(n + 2);
for (int i = 0; i <= n + 1; ++i) {
L[i] = i - 1;
R[i] = i + 1;
}
L[0] = 0; R[0] = 1; // Head giả
L[n + 1] = n; R[n + 1] = n + 1; // Tail giả
for (int k = 0; k < m; ++k) {
int i, j;
cin >> i >> j;
// Xóa i khỏi vị trí cũ (L[R[i]] = L[i]; R[L[i]] = R[i];)
R[L[i]] = R[i];
L[R[i]] = L[i];
// Chèn i vào trước j
// Nếu j == 0, chèn vào trước node 0? Không, chèn vào trước node đầu tiên thực sự?
// Đề bài: j=0 -> cuối hàng.
// Nếu dùng node 0 là head, node n+1 là tail.
// Chèn vào cuối: tức là chèn vào trước node tail (n+1).
// Nếu j=0, ta coi j = n+1 (tail).
int target = j;
if (j == 0) target = n + 1;
// Chèn i vào trước target
L[i] = L[target];
R[i] = target;
R[L[target]] = i;
L[target] = i;
}
// Xuất kết quả
// Duyệt từ R[0] (phần tử đầu tiên) đến khi gặp n+1
int curr = R[0];
while (curr != n + 1) {
cout << curr << " ";
curr = R[curr];
}
cout << endl;
return 0;
}
- Time Complexity: O(m)
- Space Complexity: O(n)
Đây là cách tiếp cận tối ưu nhất. Bài toán yêu cầu chèn/xóa liên tục trong một danh sách, đây là thế mạnh của cấu trúc dữ liệu Linked List. Tuy nhiên, thay vì dùng con trỏ, ta dùng mảng để lưu vị trí của node bên trái và bên phải (mô phỏng doubly linked list). Để xử lý hiệu quả việc chèn vào cuối hàng (khi j=0) mà không phải duyệt toàn bộ danh sách để tìm phần tử cuối, ta sử dụng 2 node giả (sentinel nodes): node 0 làm đầu giả và node n+1 làm cuối giả. Ban đầu, hàng người thật nằm giữa 0 và n+1. Khi j=0, ta thực hiện chèn vào trước node n+1. Mỗi thao tác chỉ mất O(1) thời gian.
Cách Mô phỏng bằng Vector (Xóa và Chèn)
// Pseudocode cho cách dùng vector
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
freopen("photo.inp", "r", stdin);
freopen("photo.out", "w", stdout);
int n, m;
cin >> n >> m;
vector<int> arr;
for(int i = 1; i <= n; i++) arr.push_back(i);
for(int k = 0; k < m; k++) {
int i, j;
cin >> i >> j;
// Tìm và xóa i
auto it = find(arr.begin(), arr.end(), i);
if (it != arr.end()) {
arr.erase(it);
}
// Nếu j == 0, chèn vào cuối
if (j == 0) {
arr.push_back(i);
} else {
// Tìm vị trí j và chèn vào trước nó
auto pos = find(arr.begin(), arr.end(), j);
arr.insert(pos, i);
}
}
for(int x : arr) cout << x << " ";
cout << endl;
return 0;
}
- Time Complexity: O(m * n)
- Space Complexity: O(n)
Sử dụng vector (mảng động) để lưu trữ hàng người. Với mỗi giao dịch, ta phải tìm vị trí của VĐV i và VĐV j trong mảng. Trong trường hợp xấu nhất, việc tìm kiếm này mất O(n). Việc xóa và chèn vào vector cũng có độ phức tạp O(n) do phải di chuyển các phần tử. Với m giao dịch, độ phức tạp tổng cộng là O(m*n). Cách này đơn giản để viết nhưng sẽ chạy rất chậm và bị quá thời gian nếu n, m lớn (ví dụ > 10^5).
Cách Mô phỏng mảng liên tục với đánh dấu
// Pseudocode cho cách dùng mảng đánh dấu
#include <iostream>
#include <vector>
using namespace std;
int main() {
// freopen ...
int n, m;
cin >> n >> m;
vector<int> pos(n + 1); // Vị trí hiện tại của VĐV
vector<int> order(n); // VĐV ở vị trí k
for(int i = 1; i <= n; i++) {
pos[i] = i;
order[i-1] = i;
}
int max_idx = n;
for(int k = 0; k < m; k++) {
int i, j;
cin >> i >> j;
int cur_pos = pos[i];
// Xóa i khỏi vị trí cũ: đánh dấu -1
order[cur_pos - 1] = -1;
// Nếu j == 0, chèn vào cuối
if (j == 0) {
order[max_idx] = i;
pos[i] = max_idx + 1;
max_idx++;
} else {
// Tìm vị trí j
int target_pos = pos[j];
// Chèn vào trước j: cần dời các phần tử sau target_pos
// Điều này rất chậm O(n)
// ... logic dịch chuyển ...
}
// ...
}
return 0;
}
- Time Complexity: O(m * n)
- Space Complexity: O(n)
Cố gắng lưu trạng thái hàng bằng mảng static. Tuy nhiên, việc chèn vào giữa mảng yêu cầu dời các phần tử phía sau, dẫn đến độ phức tạp O(n) cho mỗi thao tác. Đây là một cách tiếp cận sai lầm về mặt thuật toán cho bài toán này, tương tự như cách dùng vector.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(m) | O(n) | Mô phỏng bằng Danh sách liên kết kép (Double Linked List) |
| 2 | O(m * n) | O(n) | Mô phỏng bằng Vector (Xóa và Chèn) |
| 3 | O(m * n) | O(n) | Mô phỏng mảng liên tục với đánh dấu |
Bài học kinh nghiệm
- Bài toán là bài toán điển hình về cấu trúc dữ liệu Linked List (Danh sách liên kết) do các thao tác chèn và xóa liên tục.
- Việc xử lý 'đầu hàng' và 'cuối hàng' có thể được đơn giản hóa bằng cách sử dụng các node giả (sentinel nodes) hoặc dummy nodes.
- Sử dụng mảng để mô phỏng con trỏ (thuộc tính left và right) giúp tránh tràn stack và truy cập nhanh trong C++.
Lỗi thường gặp
- Quên cập nhật cả con trỏ trái và phải của các node liên quan khi xóa hoặc chèn một node.
- Xử lý sai trường hợp j = 0 (cuối hàng) nếu không có cơ chế sentinel hoặc biến lưu tail.
- Lỗi truy cập ngoài biên mảng nếu chỉ dùng mảng size n và không xử lý các phần tử đầu/cuối đặc biệt.
Bình luận