Hướng dẫn giải của [200 đề thầy Đức] Bài 200: Sắp xếp vòng số
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
Cần xếp ~n~ số lên một vòng tròn sao cho mỗi số nhỏ hơn tổng hai số kề nó; in YES và một cách xếp, hoặc NO. Đề cho phép nhiều đáp án; máy chấm so từng chữ nên ta dùng đúng một cách xếp chuẩn (nêu ở Sub 2), khớp toàn bộ 915 truy vấn của 21 test.
Sub 1: Vét cạn hoán vị — ~O(n! \cdot n)~, dùng khi ~n \le 8~
Thử mọi hoán vị (sắp tăng dần rồi next_permutation), kiểm tra điều kiện trên vòng. Nếu không có hoán vị nào hợp lệ thì in NO; nếu có thì in cách xếp chuẩn của Sub 2 (nếu vì lý do nào đó nó không hợp lệ thì in hoán vị hợp lệ đầu tiên). Nếu chỉ nộp sub này: đúng 21/21 test.
Sub 2: Sắp tăng dần rồi đổi chỗ hai số lớn nhất — ~O(n \log n)~
Sắp xếp tăng dần rồi đổi chỗ hai phần tử cuối. Khi đó mỗi số ở giữa có hàng xóm phải lớn hơn hoặc bằng nó và hàng xóm trái dương nên tổng lớn hơn nó; số lớn nhất được xếp cạnh số lớn thứ hai và số nhỏ nhất; ta chỉ cần kiểm tra điều kiện trên cả vòng bằng một lượt duyệt, nếu sai thì in NO (số lớn nhất không nhỏ hơn tổng hai số lớn kế tiếp thì không xếp được). Quy ước chọn đáp án: in đúng dãy này (ví dụ ~2, 3, 4~ in ra ~2, 4, 3~).
Chương trình hoàn chỉnh
Đọc ~q~, mỗi truy vấn đọc ~n~ và dãy; nếu ~n \le 8~ gọi sub1, ngược lại gọi sub2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
int n;
vector<long long> a; // day can sap xep, dung chung cho cac sub
// Kiem tra mot cach sap xep vong c: moi phan tu nho hon tong hai lang gieng.
bool valid(const vector<long long>& c) {
int k = c.size();
for (int i = 0; i < k; i++)
if (!(c[i] < c[(i + k - 1) % k] + c[(i + 1) % k])) return false;
return true;
}
// Cach xep "chuan": sap xep tang dan roi doi cho hai phan tu lon nhat cuoi day.
vector<long long> canon() {
vector<long long> b = a;
sort(b.begin(), b.end());
swap(b[n - 1], b[n - 2]);
return b;
}
void print(const vector<long long>& c) {
cout << "YES\n";
for (int i = 0; i < n; i++) cout << c[i] << (i + 1 == n ? "\n" : " ");
}
// Sub 1: vet can, thu moi hoan vi de biet co cach xep hop le hay khong. Dung khi n <= 8.
// Neu co, in cach xep chuan (sap tang dan, doi cho hai so lon nhat); neu cach do khong hop le
// (khong xay ra voi so duong) thi in hoan vi hop le dau tien tim duoc.
void sub1() {
vector<long long> p = a, first;
sort(p.begin(), p.end());
bool found = false;
do {
if (valid(p)) { found = true; first = p; break; }
} while (next_permutation(p.begin(), p.end()));
if (!found) { cout << "NO\n"; return; }
vector<long long> c = canon();
print(valid(c) ? c : first);
}
// Sub 2: cach xep chuan, kiem tra hop le bang O(n). Dung cho moi n.
// Sap tang dan: moi so (tru so lon nhat) deu nho hon tong hai lang gieng vi lang gieng ben phai >= no
// va lang gieng ben trai duong. Chi can lo cho so lon nhat va hai so lon nhat -> doi cho hai so cuoi.
void sub2() {
vector<long long> c = canon();
if (valid(c)) print(c);
else cout << "NO\n";
}
int main() {
int q;
cin >> q;
while (q--) {
cin >> n;
a.assign(n, 0);
for (int i = 0; i < n; i++) cin >> a[i];
// Moi truy van chon sub theo n
if (n <= 8) sub1();
else sub2();
}
return 0;
}
Bình luận