Hướng dẫn giải của [200 đề thầy Đức] Bài 197: Cân bằng giá
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
Mỗi truy vấn cho dãy giá a_1, …, a_n và số k. Cần tìm giá mới b nguyên, b ≥ 0, lớn nhất sao cho |a_i - b| ≤ k với mọi i. Nếu không có b nào thì in -1. Vì mỗi sản phẩm được giữ nguyên giá hoặc đổi tối đa một lần, và giữ nguyên tức là b = a_i (khi đó lệch bằng 0 ≤ k), nên điều kiện trên là đủ.
Sub 1: Vét cạn theo giá trị b — ~O(V·N)~
Bắt đầu từ b = min(a) + k (không thể lớn hơn), rồi giảm dần b về 0. Với mỗi b, kiểm tra toàn bộ dãy. b đầu tiên thỏa mãn là đáp án. Cách này đúng nhưng khi k lớn, số giá trị cần thử lên tới 10^8, nên chỉ đạt 4/21 test, còn lại quá giờ.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> q;
while (q--) {
int n;
long long k;
cin >> n >> k;
vector<long long> a(n);
for (auto &x : a) cin >> x;
// Vét cạn: thử lần lượt các giá b từ lớn xuống 0, b đầu tiên thỏa mãn là đáp án.
// b không thể lớn hơn min(a) + k, nên bắt đầu từ đó.
long long start = LLONG_MAX;
for (long long x : a) start = min(start, x + k);
long long ans = -1;
for (long long b = start; b >= 0 && ans == -1; b--) {
bool ok = true;
for (long long x : a)
if (llabs(x - b) > k) { ok = false; break; }
if (ok) ans = b;
}
cout << ans << "\n";
}
return 0;
}
Sub 2: Công thức đoạn giao — ~O(N)~
Điều kiện |a_i - b| ≤ k với mọi i tương đương max(a) - k ≤ b ≤ min(a) + k. Vì vậy b lớn nhất có thể là min(a) + k, miễn là nó không nhỏ hơn max(a) - k. Nếu không thỏa thì in -1. Cần long long vì a_i + k có thể đến 2·10^8. Đạt 21/21 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> q;
while (q--) {
int n;
long long k;
cin >> n >> k;
long long mn = LLONG_MAX, mx = LLONG_MIN;
for (int i = 0; i < n; i++) {
long long x;
cin >> x;
mn = min(mn, x);
mx = max(mx, x);
}
// Điều kiện |a_i - b| <= k với mọi i <=> mx - k <= b <= mn + k.
// b lớn nhất là mn + k, cần kiểm tra mn + k >= mx - k (và b >= 0 luôn đúng vì a_i >= 1).
long long b = mn + k;
if (b < mx - k || b < 0) cout << -1 << "\n";
else cout << b << "\n";
}
return 0;
}
Bình luận