Hướng dẫn giải của Biển số đẹp_PY
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.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
, , ,
Hiểu bài toán
Bài toán yêu cầu tìm chi phí tối thiểu để trong một chuỗi số độ dài N có ít nhất K chữ số giống nhau. Chi phí để thay đổi một chữ số từ A thành B là |A - B|. Chúng ta cần chọn một chữ số mục tiêu (từ 0 đến 9) và thay đổi các chữ số khác để biến tối đa K chữ số trong chuỗi thành chữ số mục tiêu đó với tổng chi phí là nhỏ nhất.
Các cách tiếp cận
Cách Brute Force với sắp xếp
#include <bits/stdc++.h>
using namespace std;
int main() {
freopen("fnumber.inp", "r", stdin);
freopen("fnumber.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
string s; cin >> s;
int ans = 1e9;
// Thử tất cả các chữ số mục tiêu từ 0 đến 9
for (int d = 0; d <= 9; d++) {
vector<int> cost;
// Tính chi phí đổi từng chữ số về d
for (char c : s) cost.push_back(abs((c - '0') - d));
// Sắp xếp để lấy k chi phí nhỏ nhất
sort(cost.begin(), cost.end());
int sum = 0;
for (int i = 0; i < k; i++) sum += cost[i];
ans = min(ans, sum);
}
cout << ans;
}
- Time Complexity: O(10 * N log N)
- Space Complexity: O(N)
Giải pháp này thử tất cả 10 khả năng chữ số mục tiêu (0-9). Với mỗi chữ số mục tiêu, nó tính chi phí đổi tất cả các chữ số trong chuỗi về chữ số đó, lưu vào vector, sắp xếp và lấy k chi phí nhỏ nhất. Tuy nhiên, cách này không tối ưu vì nó tính chi phí cho cả những chữ số đã đúng (chi phí 0) và không tối ưu hóa việc chỉ lấy đúng k phần tử.
Cách Tối ưu hóa với số lượng chữ số sẵn có
#include <bits/stdc++.h>
using namespace std;
int main() {
freopen("fnumber.inp", "r", stdin);
freopen("fnumber.out", "w", stdout);
int n, k;
cin >> n >> k;
string s;
cin >> s;
int r = 1e9;
for (int d = 0; d < 10; d++) {
vector<int> v;
int c = 0; // Đếm số chữ số đã bằng d
for (char ch : s) {
int x = ch - '0';
if (x == d) c++;
else v.push_back(abs(x - d));
}
// Nếu đủ số chữ số bằng d rồi thì chi phí là 0
if (c >= k) { r = 0; break; }
sort(v.begin(), v.end());
int need = k - c; // Số chữ số cần đổi thêm
if (need <= (int)v.size()) {
int sum = 0;
for (int i = 0; i < need; i++) sum += v[i];
r = min(r, sum);
}
}
cout << r;
}
- Time Complexity: O(10 * N log N)
- Space Complexity: O(N)
Cải tiến từ giải pháp đầu tiên: Thay vì luôn lấy K chi phí nhỏ nhất, ta chỉ cần lấy (K - sốlượngchữsốđã_đúng) chi phí nhỏ nhất. Điều này loại bỏ các chi phí bằng 0 không cần thiết ra khỏi danh sách, giúp logic chính xác hơn một chút nhưng độ phức tạp vẫn tương đương.
Cách Tối ưu với Heap (Priority Queue)
#include <bits/stdc++.h>
using namespace std;
int main() {
freopen("fnumber.inp", "r", stdin);
freopen("fnumber.out", "w", stdout);
int n, k;
cin >> n >> k;
string s;
cin >> s;
int ans = 1e9;
for (int d = 0; d <= 9; d++) {
priority_queue<int> pq; // Max heap để lưu chi phí nhỏ nhất
int cnt = 0; // Đếm số chữ số đã bằng d
for (char c : s) {
int digit = c - '0';
if (digit == d) {
cnt++;
} else {
int cost = abs(digit - d);
pq.push(cost);
if (pq.size() > k - cnt) {
pq.pop(); // Loại bỏ chi phí lớn nhất nếu vượt quá số lượng cần
}
}
}
if (cnt >= k) {
ans = 0;
break;
}
// Tính tổng chi phí nhỏ nhất
if (cnt + pq.size() >= k) {
int sum = 0;
while (!pq.empty()) {
sum += pq.top();
pq.pop();
}
ans = min(ans, sum);
}
}
cout << ans;
return 0;
}
- Time Complexity: O(10 * N log K)
- Space Complexity: O(K)
Giải pháp tối ưu nhất: Dùng Heap (Priority Queue) để duy trì K chi phí nhỏ nhất mà không cần sắp xếp toàn bộ mảng. Với mỗi chữ số, ta duy trì một max heap chứa các chi phí nhỏ nhất. Khi heap đầy, ta loại bỏ phần tử lớn nhất. Độ phức tạp log K thay vì log N, tiết kiệm bộ nhớ đáng kể.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(10 * N log N) | O(N) | Brute Force với sắp xếp |
| 2 | O(10 * N log N) | O(N) | Tối ưu hóa với số lượng chữ số sẵn có |
| 3 | O(10 * N log K) | O(K) | Tối ưu với Heap (Priority Queue) |
Bài học kinh nghiệm
- Vì chỉ có 10 chữ số nên có thể brute force tất cả các chữ số mục tiêu từ 0 đến 9.
- Với mỗi chữ số mục tiêu, ta chỉ quan tâm đến K chi phí thay đổi nhỏ nhất (hoặc K - sốlượngđã_đúng chi phí nhỏ nhất).
- Sử dụng Heap (Priority Queue) giúp giảm độ phức tạp từ O(N log N) xuống O(N log K) và tiết kiệm bộ nhớ.
Lỗi thường gặp
- Không xử lý trường hợp đã có đủ K chữ số giống nhau sẵn (chi phí = 0).
- Lấy nhầm K chi phí nhỏ nhất thay vì chỉ lấy số lượng cần thiết khi đã có sẵn một số chữ số.
- Quên kiểm tra điều kiện biên khi số lượng chữ số cần đổi lớn hơn số lượng chữ số có thể đổi được.
Bình luận