Hướng dẫn giải của [200 đề thầy Đức] Bài 158: Sức mạnh
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
Mỗi chiến binh của đội mình phải tiêu diệt được ít nhất một chiến binh đối phương, và chiến binh $A$ tiêu diệt được $B$ khi $A > B$. Ví dụ 2 cho thấy không đủ chỉ là "mỗi chiến binh mình có một đối phương yếu hơn": hai chiến binh mình cùng sức 2 không thể cùng hạ một đối phương sức 1 và đều được tính là thắng. Vì vậy bài toán là tìm một ghép cặp hoàn chỉnh: mỗi chiến binh mình ghép với một đối phương khác nhau mà mạnh hơn.
Sub 1: Vét cạn bằng ghép cặp Kuhn — ~O(N^3)~, dùng khi ~N \le 200~
Xây đồ thị hai phía: cạnh $(i, j)$ có khi $ai > bj$. Dùng thuật toán Kuhn (tìm đường tăng quảng) để tìm ghép cặp cực đại. Nếu có chiến binh mình không tìm được đối phương nào để ghép thì đáp án là No.
Kết quả chạy riêng sub này: đúng 16/21 test (5 test quá giờ, đều có $N$ lớn hơn miền của sub này).
Sub 2: Sắp xếp hai dãy — ~O(N \log N)~
Sắp xếp tăng dần cả $a$ và $b$. Đội mình thắng khi và chỉ khi $ai > bi$ với mọi $i$: ghép chiến binh yếu nhất của mình với đối phương yếu nhất, và cứ thế. Nếu một cặp $ai \le bi$ thì không có cách ghép nào đủ.
Bẫy cần chú ý: phải so sánh dấu ngặt ($ai > bi$, không phải $\ge$) vì đề yêu cầu tiêu diệt được khi sức mạnh hơn hẳn.
Chương trình hoàn chỉnh
Chương trình đọc $N$ và hai dãy. Nếu $N \le 200$ thì gọi sub1, ngược lại gọi sub2. Khi đi thi, sub1 vẫn ăn điểm các test nhỏ nếu chưa làm được sub2.
#include <bits/stdc++.h>
using namespace std;
int N;
vector<long long> a, b; // sức mạnh của đội mình (a) và đội đối phương (b), chỉ số từ 0
// Mỗi chiến binh của mình phải tiêu diệt được một đối phương, và mỗi đối phương bị một chiến binh
// tiêu diệt (không ghép trùng). Đây là bài ghép cặp: đội mình thắng khi có ghép cặp hoàn chỉnh
// sao cho a[i] > b[j] ở mọi cặp.
// Thuật toán Kuhn (đường tăng quảng) cho bài ghép cặp
vector<int> matchB; // matchB[j] = chiến binh mình đang ghép với đối phương j
vector<bool> used;
bool tryKuhn(int i) {
for (int j = 0; j < N; j++) {
if (a[i] <= b[j] || used[j]) continue; // chỉ ghép được nếu a[i] > b[j]
used[j] = true;
if (matchB[j] == -1 || tryKuhn(matchB[j])) {
matchB[j] = i;
return true;
}
}
return false;
}
// Sub 1: vét cạn — tìm ghép cặp hoàn chỉnh bằng thuật toán Kuhn. Dùng khi N <= 200
void sub1() {
matchB.assign(N, -1);
bool ok = true;
for (int i = 0; i < N && ok; i++) {
used.assign(N, false);
if (!tryKuhn(i)) ok = false; // một chiến binh mình không tìm được đối phương nào
}
cout << (ok ? "Yes" : "No") << "\n";
}
// Sub 2: sắp xếp hai dãy tăng dần; đội mình thắng khi a[i] > b[i] với mọi i.
// Đây là cách ghép tham lam tối ưu: ghép mạnh nhất với mạnh nhất. O(N log N).
void sub2() {
sort(a.begin(), a.end());
sort(b.begin(), b.end());
bool ok = true;
for (int i = 0; i < N; i++)
if (a[i] <= b[i]) { ok = false; break; }
cout << (ok ? "Yes" : "No") << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N;
a.resize(N);
b.resize(N);
for (int i = 0; i < N; i++) cin >> a[i];
for (int i = 0; i < N; i++) cin >> b[i];
if (N <= 200) sub1(); // N nhỏ: Kuhn cho chắc
else sub2(); // N lớn: sắp xếp
return 0;
}
Bình luận