Hướng dẫn giải của [200 đề thầy Đức] Bài 77: Thay đổi âm lượng
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 lượng hiện tại là $a$, cần đưa về $b$. Mỗi lần nhấn nút đổi âm lượng $\pm 1$, $\pm 2$ hoặc $\pm 5$, và âm lượng không được nhỏ hơn $0$. Tìm số lần nhấn ít nhất.
Sub 1: Vét cạn số lần nhấn nút 5 và nút 2 — ~O(d^2)~ với $d = |a - b|$
Gọi $d = |a - b|$. Thử mọi số lần $k$ nhấn nút 5 và mọi số lần $j$ nhấn nút 2; phần còn lại $d - 5k - 2j$ nhấn nút 1. Lấy tổng số lần nhấn nhỏ nhất. Cách này đúng nhưng chậm khi $d$ lớn (đạt 6/21 test, 15 test quá giờ, không sai test nào).
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
// Đọc hết dữ liệu trước rồi mới tính, để không làm nghẽn luồng nhập.
vector<pair<long long, long long>> qs(T);
for (auto &p : qs) cin >> p.first >> p.second;
for (auto &p : qs) {
long long a = p.first, b = p.second;
long long d = llabs(a - b); // quãng cần đi, mỗi nút đổi âm lượng d một lượng 1, 2 hoặc 5
// Vét cạn: thử mọi số lần dùng nút 5 (k) và nút 2 (j), phần còn lại dùng nút 1.
// Tổng số lần nhấn = k + j + (phần còn lại); lấy số ít nhất.
long long best = LLONG_MAX;
for (long long k = 0; 5 * k <= d; k++) {
long long r = d - 5 * k;
for (long long j = 0; 2 * j <= r; j++) {
long long ones = r - 2 * j;
best = min(best, k + j + ones);
}
}
cout << best << "\n";
}
return 0;
}
Sub 2: Tham lam theo bước lớn nhất — ~O(1)~
Có thể đi đúng quãng $d$ bằng các bước 5, 2, 1 mà không xuống dưới $\min(a, b) \ge 0$: khi giảm, chỉ cần không đi quá $b$; khi tăng thì không có giới hạn trên. Bài toán trở thành đổi $d$ thành tổng các số $1, 2, 5$ với ít số hạng nhất.
Tham lam: lấy càng nhiều bước 5 càng tốt, rồi xét phần dư $r = d \bmod 5$:
- $r = 0$: 0 lần thêm;
- $r = 1$ hoặc $r = 2$: 1 lần thêm (bước 1 hoặc bước 2);
- $r = 3$ hoặc $r = 4$: 2 lần thêm ($2 + 1$ hoặc $2 + 2$).
Đáp án là $\lfloor d/5 \rfloor$ cộng phần thêm. Ví dụ $a = 4, b = 0$: $d = 4$, đáp án $2$. Ví dụ $a = 5, b = 14$: $d = 9$, $1 \cdot 5 + 2 + 2$ nên đáp án $3$.
Bẫy cần chú ý: $a$ có thể lớn hơn $b$, nên phải lấy trị tuyệt đối của hiệu.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
long long a, b;
cin >> a >> b;
// Có thể đi đúng quãng d = |a - b| bằng các bước 5, 2, 1 mà không xuống dưới 0
// (luôn giảm/tăng sao cho không vượt quá b, nên không bao giờ âm).
// Bài toán là đổi d thành tổng các số 1, 2, 5 với ít số hạng nhất:
// lấy càng nhiều 5 càng tốt, phần dư r = d mod 5 (0..4) cần:
// r = 0: 0 lần; r = 1: 1 lần (1); r = 2: 1 lần (2); r = 3: 2 lần (2+1); r = 4: 2 lần (2+2).
long long d = llabs(a - b);
long long k = d / 5, r = d % 5;
long long extra;
if (r == 0) extra = 0;
else if (r == 1 || r == 2) extra = 1;
else extra = 2;
cout << k + extra << "\n";
}
return 0;
}
Bình luận