Hướng dẫn giải của [200 đề thầy Đức] Bài 7: Những con chuột
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
~N~ con chuột và ~N~ cái tổ nằm trên một trục, mỗi bước đi mất 1 phút, mỗi vị trí chứa tối đa một con chuột. Tìm thời gian ít nhất để con chuột cuối cùng chui được vào tổ.
Sub 1: Thử mọi cách ghép — ~O(N! \cdot N)~, dùng khi ~N \le 8~
Thử mọi hoán vị của danh sách tổ (đã sắp xếp), ghép chuột thứ ~i~ với tổ thứ ~i~ của hoán vị. Thời gian của cách ghép là ~\max |m_i - h_i|~. Lấy cách có thời gian nhỏ nhất.
Nếu chỉ nộp sub này: đúng 1/21 test.
Sub 2: Ghép theo thứ tự — ~O(N \log N)~, dùng khi mọi trường hợp còn lại
Sắp xếp chuột và tổ tăng dần rồi ghép theo thứ tự. Đây là cách ghép cho thời gian lớn nhất nhỏ nhất, vì nếu hai đường đi giao nhau thì đổi chỗ không làm tệ hơn.
Nếu chỉ nộp sub này: đúng 21/21 test.
Chương trình hoàn chỉnh
Chương trình đọc ~T~ rồi từng bộ. Nếu ~N \le 8~ thì gọi sub1, ngược lại gọi sub2. Ví dụ: chuột ~4, -4, 2~ và tổ ~4, 0, 5~ cho 4.
#include <bits/stdc++.h>
using namespace std;
int N;
vector<int> mice, holes;
// Sub 1: vet can. Thu moi cach ghep chuot voi to (hoan vi cua day to),
// lay cach cho thoi gian lon nhat nho nhat. O(N! * N), dung khi N <= 8.
void sub1() {
vector<int> h = holes;
sort(h.begin(), h.end());
long long best = LLONG_MAX;
do {
long long mx = 0;
for (int i = 0; i < N; i++) mx = max(mx, (long long)abs(mice[i] - h[i]));
best = min(best, mx);
} while (next_permutation(h.begin(), h.end()));
cout << best << "\n";
}
// Sub 2: sap xep ca chuot va to, ghep chuot thu i voi to thu i.
// Thoi gian can la max |m_i - h_i|. Day la cach ghep tot nhat khi co the ghep tuy y. O(N log N).
void sub2() {
vector<int> m = mice, h = holes;
sort(m.begin(), m.end());
sort(h.begin(), h.end());
long long mx = 0;
for (int i = 0; i < N; i++) mx = max(mx, (long long)abs(m[i] - h[i]));
cout << mx << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
cin >> N;
mice.assign(N, 0);
holes.assign(N, 0);
for (int i = 0; i < N; i++) cin >> mice[i];
for (int i = 0; i < N; i++) cin >> holes[i];
if (N <= 8) sub1();
else sub2();
}
return 0;
}
Bình luận