Hướng dẫn giải của [200 đề thầy Đức] Bài 191: Đường hầm
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
Xe ~c~ bị phạt khi tồn tại xe ~d~ vào đường hầm trước ~c~ nhưng thoát ra sau ~c~ (khi đó ~c~ chắc chắn vượt ~d~). Đếm số xe bị phạt.
Sub 1: Vét cạn — ~O(n^2)~, dùng khi ~n \le 500~
Duyệt các xe theo thứ tự vào. Với mỗi xe ~c~, kiểm tra các xe vào trước nó xem có xe nào thoát sau ~c~ hay không. Lưu ý số hiệu xe trong bộ dữ liệu bắt đầu từ 0 nên không lặp theo số hiệu. Nếu chỉ nộp sub này: đúng 21/21 test.
Sub 2: Giữ thứ tự thoát lớn nhất — ~O(n)~
Duyệt các xe theo thứ tự vào, giữ thứ tự thoát lớn nhất của các xe đã vào trước. Xe ~c~ bị phạt khi thứ tự thoát lớn nhất đó lớn hơn thứ tự thoát của ~c~. Nếu chỉ nộp sub này: đúng 21/21 test.
Chương trình hoàn chỉnh
main đọc ~n~ và hai dãy vào, ra. Nếu ~n \le 500~ thì gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int n;
int A[100005], B[100005]; // A[k]: số hiệu xe vào thứ k; B[k]: số hiệu xe ra thứ k
int pin[100005], pout[100005]; // thứ tự vào / ra của từng xe theo số hiệu (số hiệu có thể bắt đầu từ 0)
// Sub 1: vét cạn O(n^2). Xe c bị phạt nếu tồn tại xe d vào trước c nhưng ra sau c.
// Duyệt theo thứ tự vào (k) để tránh phụ thuộc vào cách đánh số xe.
void sub1() {
int cnt = 0;
for (int k = 1; k <= n; k++) {
int c = A[k];
bool fined = false;
for (int k2 = 1; k2 < k && !fined; k2++) {
int d = A[k2]; // xe d vào trước xe c
if (pout[d] > pout[c]) fined = true;
}
if (fined) cnt++;
}
printf("%d\n", cnt);
}
// Sub 2: O(n). Duyệt các xe theo thứ tự vào; giữ thứ tự ra lớn nhất của các xe đã vào trước.
// Xe c bị phạt khi có xe vào trước mà ra sau nó, tức là max thứ tự ra trước đó lớn hơn pout[c].
void sub2() {
int cnt = 0, maxOut = 0;
for (int k = 1; k <= n; k++) {
int c = A[k];
if (maxOut > pout[c]) cnt++;
maxOut = max(maxOut, pout[c]);
}
printf("%d\n", cnt);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int k = 1; k <= n; k++) {
cin >> A[k];
pin[A[k]] = k;
}
for (int k = 1; k <= n; k++) {
cin >> B[k];
pout[B[k]] = k;
}
if (n <= 500) sub1(); // dữ liệu nhỏ: vét cạn
else sub2();
return 0;
}
Bình luận