Hướng dẫn giải của [VT Thiếu nhi] BÀI 10: SEQGAME
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
Cần tìm giá trị nhỏ nhất của |bi + cj| trên mọi cặp (i, j). Đây là bài tìm hai số, mỗi số lấy từ một dãy, có tổng gần 0 nhất.
Sub 1: Vét cạn — ~O(n^2)~, dùng khi ~n \le 1000~
Thử mọi cặp (i, j), tính |bi + cj| và lấy giá trị nhỏ nhất. Nếu chỉ nộp sub này: đúng 30/50 test (các test có n lớn chạy quá giờ).
Sub 2 (đầy đủ): Sắp xếp và tìm kiếm nhị phân — ~O(n \log n)~
Với mỗi bi, |bi + cj| nhỏ nhất khi cj gần -bi nhất. Sắp xếp dãy c, dùng lower_bound tìm vị trí -bi, rồi chỉ cần xét hai phần tử đứng ngay trước và sau vị trí đó.
Bẫy: tổng bi + cj có thể vượt 2 \cdot 10^9, dùng long long.
Nếu chỉ nộp sub này: đúng 50/50 test.
Chương trình hoàn chỉnh
Hàm main đọc n và hai dãy. Nếu n \le 1000 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;
long long b[100005], c[100005]; // day b va day c, chi so 1..n
// Sub 1: vet can O(n^2) - thu moi cap (b_i, c_j), lay gia tri |b_i + c_j| nho nhat. Dung khi n <= 1000.
void sub1() {
long long best = LLONG_MAX;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
best = min(best, llabs(b[i] + c[j]));
cout << best << "\n";
}
// Sub 2: day du O(n log n).
// |b_i + c_j| nho nhat <=> c_j gan -b_i nhat. Sap xep c, voi moi b_i tim vi tri -b_i bang lower_bound
// roi xet hai phan tu ke canh.
void sub2() {
vector<long long> s(c + 1, c + n + 1);
sort(s.begin(), s.end());
long long best = LLONG_MAX;
for (int i = 1; i <= n; i++) {
long long target = -b[i];
auto it = lower_bound(s.begin(), s.end(), target);
if (it != s.end()) best = min(best, llabs(b[i] + *it));
if (it != s.begin()) best = min(best, llabs(b[i] + *prev(it)));
}
cout << best << "\n";
}
int main() {
freopen("SEQGAME.INP", "r", stdin);
freopen("SEQGAME.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) cin >> b[i];
for (int i = 1; i <= n; i++) cin >> c[i];
if (n <= 1000) sub1(); // n nho: vet can
else sub2();
return 0;
}
Bình luận