Hướng dẫn giải của [200 đề thầy Đức] Bài 71: Chia nhó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
Chia ~n~ học sinh có trình độ khác nhau thành ít nhất các nhóm, sao cho không có hai học sinh cùng nhóm lệch nhau đúng 1.
Sub 1: Thử mọi cặp — ~O(n^2)~, dùng khi ~n \le 2000~
Thử mọi cặp học sinh. Nếu có cặp lệch đúng 1 thì cần 2 nhóm, không thì 1 nhóm.
Nếu chỉ nộp sub này: đúng 21/21 test.
Sub 2: Sắp xếp — ~O(n \log n)~, dùng khi mọi trường hợp còn lại
Sắp xếp trình độ tăng dần, hai số lệch đúng 1 sẽ đứng cạnh nhau, nên chỉ cần kiểm tra các cặp liên tiếp.
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~ bộ dữ liệu. Với mỗi bộ, nếu ~n \le 2000~ thì gọi sub1, ngược lại gọi sub2. Các cặp lệch đúng 1 tạo thành các dãy số liên tiếp, đồ thị này hai màu luôn đủ, nên đáp án chỉ là 1 hoặc 2.
#include <bits/stdc++.h>
using namespace std;
int n;
vector<long long> a; // trinh do cac hoc sinh (khac nhau doi mot)
// Lop co hai hoc sinh lech nhau dung 1 thi phai xep vao nhom khac nhau.
// Do cac cap lech 1 tao thanh cac duong (day so lien tiep) nen 2 nhom luon du.
// Vi vay dap an la 1 (khong co cap lech 1) hoac 2 (co it nhat mot cap).
// Sub 1: vet can. Thu moi cap hoc sinh. O(n^2), dung khi n <= 2000.
void sub1() {
bool conflict = false;
for (int i = 0; i < n && !conflict; i++)
for (int j = i + 1; j < n; j++)
if (llabs(a[i] - a[j]) == 1) {
conflict = true;
break;
}
cout << (conflict ? 2 : 1) << "\n";
}
// Sub 2: sap xep, hai so lech 1 se nam canh nhau. O(n log n).
void sub2() {
vector<long long> b = a;
sort(b.begin(), b.end());
bool conflict = false;
for (int i = 0; i + 1 < n; i++)
if (b[i + 1] - b[i] == 1) {
conflict = true;
break;
}
cout << (conflict ? 2 : 1) << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
cin >> n;
a.assign(n, 0);
for (int i = 0; i < n; i++) cin >> a[i];
if (n <= 2000) sub1();
else sub2();
}
return 0;
}
Bình luận