Hướng dẫn giải của [200 đề thầy Đức] Bài 174: Chọn đội chơ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.
Hướng dẫn giải
Mỗi đội gồm đúng ba học sinh: một em giỏi toán (1), một em giỏi lập trình (2) và một em giỏi thể thao (3). Mỗi học sinh chỉ thuộc tối đa một đội. Cần tìm số đội nhiều nhất và cách chia.
Sub 1: Vét cạn — ~O(N^4)~ (theo số đội và số bộ ba)
Mỗi lần, thử lần lượt mọi bộ ba (i, j, k) chưa dùng với i giỏi toán, j giỏi lập trình, k giỏi thể thao. Lấy bộ đầu tiên tìm được làm một đội, đánh dấu ba em đó đã dùng, rồi lặp lại cho đến khi không còn bộ nào. Đạt 30/32 test, 2 test còn lại quá giờ vì số bộ ba cần thử quá lớn khi N gần 5000.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
vector<bool> used(n + 1, false);
vector<array<int, 3>> teams;
// Vét cạn: mỗi lần thử mọi bộ (i, j, k) chưa dùng, lấy bộ đầu tiên có
// đủ 3 loại: i giỏi toán (1), j giỏi lập trình (2), k giỏi thể thao (3)
while (true) {
bool found = false;
array<int, 3> best{};
for (int i = n; i >= 1 && !found; i--) {
if (used[i] || a[i] != 1) continue;
for (int j = n; j >= 1 && !found; j--) {
if (used[j] || a[j] != 2) continue;
for (int k = n; k >= 1 && !found; k--) {
if (used[k] || a[k] != 3) continue;
best = {i, j, k};
found = true;
}
}
}
if (!found) break;
for (int x : best) used[x] = true;
teams.push_back(best);
}
cout << teams.size() << "\n";
for (int t = 0; t < (int)teams.size(); t++)
cout << teams[t][0] << ' ' << teams[t][1] << ' ' << teams[t][2] << "\n";
return 0;
}
Sub 2: Gom theo năng khiếu — ~O(N)~
Gom chỉ số học sinh vào ba danh sách theo năng khiếu. Vì mỗi đội cần đúng một em mỗi loại nên số đội tối đa bằng số em của loại ít nhất. Ta lần lượt lấy phần tử cuối của ba danh sách để lập đội, cho đến khi một danh sách hết.
Bẫy cần chú ý: đề cho phép in ba số của một đội theo thứ tự bất kỳ và chấp nhận nhiều lời giải, nhưng chương trình vẫn in theo thứ tự (toán, lập trình, thể thao) để trùng với ví dụ. Nếu không có học sinh nào của một loại thì in 0. Đạt 32/32 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
// Gom chỉ số học sinh theo từng năng khiếu: 1 = toán, 2 = lập trình, 3 = thể thao
vector<int> g[4];
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
g[x].push_back(i);
}
// Mỗi đội cần đúng 1 em mỗi loại, nên số đội tối đa = min(số em mỗi loại).
// Lấy dần từ cuối mỗi danh sách (pop_back) cho đến khi hết một loại.
vector<array<int, 3>> teams;
while (!g[1].empty() && !g[2].empty() && !g[3].empty()) {
teams.push_back({g[1].back(), g[2].back(), g[3].back()});
g[1].pop_back();
g[2].pop_back();
g[3].pop_back();
}
cout << teams.size() << "\n";
for (int t = 0; t < (int)teams.size(); t++)
cout << teams[t][0] << ' ' << teams[t][1] << ' ' << teams[t][2] << "\n";
return 0;
}
Bình luận