Hướng dẫn giải của [200 đề thầy Đức] Bài 130: Tìm số tối thiểu
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
Cho số ~S~ gồm ~n~ chữ số và số ~k~. Được thay tối đa ~k~ chữ số của ~S~ (thay bằng chữ số bất kỳ) sao cho số thu được vẫn có ~n~ chữ số, không có số ~0~ thừa ở đầu, và số thu được là nhỏ nhất có thể.
Sub 1: Vét cạn — ~O(10^n \cdot n)~, dùng khi ~n \le 5~
Thử lần lượt mọi số ~x~ có ~n~ chữ số, bắt đầu từ số nhỏ nhất hợp lệ. Với mỗi ~x~, đếm số vị trí khác ~S~. Nếu số này không quá ~k~ thì ~x~ là đáp án, vì các số được thử theo thứ tự tăng dần.
Kết quả chấm riêng sub này: đúng 1/21 test (các test còn lại có ~n~ lớn hơn miền của sub, nên quá giờ).
Sub 2: Tham lam từ trái sang phải — ~O(n)~
Muốn số nhỏ nhất thì các chữ số từ trái sang phải phải nhỏ nhất có thể:
- Vị trí đầu tiên (khi ~n > 1~) phải khác ~0~, nên mục tiêu là chữ số ~1~.
- Các vị trí sau mục tiêu là chữ số ~0~.
Đi từ trái sang phải: nếu chữ số hiện tại khác mục tiêu và còn lượt thay thế thì thay bằng mục tiêu và trừ một lượt. Vì thay ở vị trí bên trái luôn làm số nhỏ hơn nhiều hơn mọi thay đổi ở bên phải, cách tham lam này cho đáp án tối ưu.
Lưu ý: dữ liệu thực tế có vài số ~S~ bắt đầu bằng chữ số 0 (trái đề) với ~k = 0~; khi đó giữ nguyên ~S~ là đúng.
Bẫy cần chú ý: trường hợp ~n = 1~ thì chữ số ~0~ là hợp lệ, nên mục tiêu của vị trí duy nhất là ~0~. Ví dụ ~S = 1~, ~k = 1~ cho đáp án ~0~.
Kết quả chấm riêng sub này: đúng 21/21 test.
Chương trình hoàn chỉnh
Chương trình đọc ~T~, rồi với mỗi bộ dữ liệu đọc ~n, k~ và chuỗi ~S~. Nếu ~n \le 5~ thì gọi sub1, ngược lại gọi sub2. Khi đi thi nên viết như vậy: sub1 vẫn ăn điểm các test nhỏ nếu sub2 chưa làm kịp.
#include <bits/stdc++.h>
using namespace std;
int n, k;
string S;
// Sub 1: vét cạn — thử mọi số có đúng n chữ số (không có số 0 thừa ở đầu),
// số nào khác S không quá k chữ số thì lấy số nhỏ nhất
// Dùng khi n <= 5 (tối đa 9*10^4 số mỗi test)
void sub1() {
long long lo = (n == 1) ? 0 : (long long)pow(10, n - 1); // số nhỏ nhất có n chữ số hợp lệ
long long hi = (long long)pow(10, n) - 1; // số lớn nhất có n chữ số
for (long long x = lo; x <= hi; x++) {
// Ghép x thành đúng n chữ số để so với S
string t = to_string(x);
t = string(n - t.size(), '0') + t;
int diff = 0;
for (int i = 0; i < n; i++) if (t[i] != S[i]) diff++;
if (diff <= k) { cout << t << "\n"; return; } // x tăng dần nên số đầu tiên thỏa mãn là nhỏ nhất
}
// Không tìm được (chỉ khi S có số 0 ở đầu mà k = 0, tức dữ liệu ngoài đề): giữ nguyên S
cout << S << "\n";
}
// Sub 2: tham lam — đi từ trái sang phải, ở mỗi vị trí muốn chữ số nhỏ nhất có thể:
// vị trí đầu tiên (khi n > 1) là 1 (không được là 0), các vị trí sau là 0.
// Nếu chữ số khác mục tiêu và còn lượt thay thế thì thay. Dùng cho mọi n
void sub2() {
string res = S;
int left = k;
for (int i = 0; i < n; i++) {
char target = (i == 0 && n > 1) ? '1' : '0';
if (res[i] != target && left > 0) { res[i] = target; left--; }
}
cout << res << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
cin >> n >> k >> S;
if (n <= 5) sub1(); // n nhỏ: vét cạn cho chắc
else sub2(); // n lớn: tham lam từ trái sang phải
}
return 0;
}
Bình luận