Hướng dẫn giải của Sắp xếp (đề HSG 9 Phú Thọ 2015-2016)
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
Cho dãy n số nguyên (n <= 10^6). Tìm các chỉ số k (1 <= k < n) sao cho sau khi sắp tăng đoạn a1..ak và đoạn a{k+1}..an thì dãy trở thành tăng. Đề dùng file SAPXEP.INP và SAPXEP.OUT.
Sub 1: Thử từng k và sắp xếp lại — ~O(n^2 \log n)~, dùng khi ~n \le 2000~
Với mỗi k, sao chép dãy, sắp hai đoạn rồi kiểm tra có tăng không. Đúng nhưng chậm.
Nếu chỉ nộp sub này: đúng 8/28 test (các test n lớn bị quá giờ).
Sub 2: Max tiền tố và min hậu tố — ~O(n)~
Sau khi sắp hai đoạn, dãy tăng khi và chỉ khi max của đoạn đầu <= min của đoạn sau. Ta tính sẵn mảng max tiền tố và min hậu tố, rồi kiểm tra từng k trong O(1). Bẫy: giá trị có thể âm, dùng long long với giá trị khởi tạo LLONGMIN, LLONGMAX.
Nếu chỉ nộp sub này: đúng 28/28 test.
Chương trình hoàn chỉnh
Main đọc n và dãy từ SAPXEP.INP. Nếu n <= 2000 gọi sub1, ngược lại gọi sub2. Khi không có k nào thì in 0 và một dòng trống.
#include <bits/stdc++.h>
using namespace std;
int n;
vector<long long> a;
// Sub 1: voi moi k, sap xep rieng doan dau va doan sau roi kiem tra tang — O(n^2 log n), dung khi n <= 2000
void sub1() {
vector<int> res;
for (int k = 1; k < n; k++) {
vector<long long> b = a;
sort(b.begin(), b.begin() + k);
sort(b.begin() + k, b.end());
if (is_sorted(b.begin(), b.end())) res.push_back(k);
}
cout << res.size() << "\n";
for (size_t i = 0; i < res.size(); i++)
cout << res[i] << (i + 1 < res.size() ? " " : "\n");
if (res.empty()) cout << "\n";
}
// Sub 2: sau khi sap xep, hai doan tao thanh day tang khi va chi khi max(doan dau) <= min(doan sau).
// Dung mang max tien to va min hau to — O(n)
void sub2() {
vector<long long> pmax(n + 1), smin(n + 2);
pmax[0] = LLONG_MIN;
for (int i = 1; i <= n; i++) pmax[i] = max(pmax[i - 1], a[i - 1]);
smin[n + 1] = LLONG_MAX;
for (int i = n; i >= 1; i--) smin[i] = min(smin[i + 1], a[i - 1]);
vector<int> res;
for (int k = 1; k < n; k++)
if (pmax[k] <= smin[k + 1]) res.push_back(k);
cout << res.size() << "\n";
for (size_t i = 0; i < res.size(); i++)
cout << res[i] << (i + 1 < res.size() ? " " : "\n");
if (res.empty()) cout << "\n";
}
int main() {
freopen("SAPXEP.INP", "r", stdin);
freopen("SAPXEP.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
a.resize(n);
for (int i = 0; i < n; i++) cin >> a[i];
if (n <= 2000) sub1();
else sub2();
return 0;
}
Bình luận