Hướng dẫn giải của Khách hàng may mắn (đề HSG 9 Phú Thọ 2022-2023)
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
Chọn đoạn $[u, v]$ theo giá trị tuyệt đối. Các $ai$ đã sắp theo $|ai|$ tăng dần nên mỗi đoạn $[u, v]$ tương ứng với một đoạn chỉ số liên tiếp $l..r$ trong dãy. Nếu $u$ và $v$ đều lấy đúng bằng $|al|$ và $|ar|$ thì hiệu $v - u$ nhỏ nhất, nên chỉ cần thử các đoạn chỉ số $l..r$.
Sub 1: Vét cạn — ~O(n^3)~, dùng khi ~n \le 200~
Thử mọi đoạn chỉ số $l..r$, đếm số $ai$ dương và số $ai$ âm trong đoạn, rồi chọn đoạn thỏa điều kiện có $v - u$ nhỏ nhất (với $u$ nhỏ nhất nếu hòa).
Nếu chỉ nộp sub này: đúng 32/40 test (8 test lớn quá giờ).
Sub 2: Cải tiến bằng tiền tố và tìm kiếm nhị phân — ~O(n \log n)~
Với mỗi $l$, cần $r$ nhỏ nhất sao cho đoạn $l..r$ có đủ $x$ số dương và $y$ số âm. Đếm số dương và số âm bằng mảng tiền tố $P$ và $Q$, số đếm tăng theo $r$ nên dùng lower_bound để tìm $r$ cho từng điều kiện, lấy $r = \max(rp, rn)$. Bẫy: nếu không đủ số phần tử thì bỏ qua $l$.
Nếu chỉ nộp sub này: đúng 40/40 test.
Chương trình hoàn chỉnh
main đọc dữ liệu, nếu $n \le 200$ thì gọi sub 1, còn lại gọi sub 2.
#include <bits/stdc++.h>
using namespace std;
int n, x, y;
long long a[200005]; // a[1..n], |a_i| tang dan (de bai cho san)
vector<int> P, Q; // P[k] = so a_i duong trong 1..k, Q[k] = so a_i am trong 1..k
// Sub 1: vet can O(n^3), dung khi n <= 200
// Thu moi doan [l, r] cua chi so (u = |a_l|, v = |a_r|), dem so duong va so am trong doan.
void sub1() {
long long bestD = -1, bestU = 0, bestV = 0;
for (int l = 1; l <= n; l++)
for (int r = l; r <= n; r++) {
int cp = 0, cn = 0;
for (int k = l; k <= r; k++) {
if (a[k] > 0) cp++;
else cn++;
}
if (cp >= x && cn >= y) {
long long u = llabs(a[l]), v = llabs(a[r]);
long long d = v - u;
if (bestD < 0 || d < bestD || (d == bestD && u < bestU)) {
bestD = d; bestU = u; bestV = v;
}
}
}
if (bestD < 0) cout << -1 << "\n";
else cout << bestU << " " << bestV << "\n";
}
// Sub 2: cai tien O(n log n), dung cho moi n
// Voi moi l, tim r nho nhat thoa ca hai dieu kien (so duong >= x, so am >= y).
// Vi so dem tang dan theo r nen dung lower_bound tren mang tien to.
void sub2() {
P.assign(n + 1, 0);
Q.assign(n + 1, 0);
for (int k = 1; k <= n; k++) {
P[k] = P[k - 1] + (a[k] > 0);
Q[k] = Q[k - 1] + (a[k] < 0);
}
long long bestD = -1, bestU = 0, bestV = 0;
for (int l = 1; l <= n; l++) {
int rp = lower_bound(P.begin() + l, P.begin() + n + 1, P[l - 1] + x) - P.begin();
int rn = lower_bound(Q.begin() + l, Q.begin() + n + 1, Q[l - 1] + y) - Q.begin();
if (rp > n || rn > n) continue; // khong du so luong
int r = max(rp, rn);
long long u = llabs(a[l]), v = llabs(a[r]);
long long d = v - u;
if (bestD < 0 || d < bestD) { // l tang dan nen u tang: lan dau gap d nho nhat la u nho nhat
bestD = d; bestU = u; bestV = v;
}
}
if (bestD < 0) cout << -1 << "\n";
else cout << bestU << " " << bestV << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> x >> y;
for (int i = 1; i <= n; i++) cin >> a[i];
if (n <= 200) sub1(); // du lieu nho: vet can
else sub2();
return 0;
}
Bình luận