Hướng dẫn cho Xâu min
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Authors:
HINT
Ý TƯỞNG: để chọn ra \(K\) kí tự trong xâu \(S\) theo thứ tự ban đầu để tạo thành số \(X\) gồm \(K\) chữ số có giá trị bé nhất thì ta cần ưu tiên các kí tự đứng trước nhỏ nhất có thể, sau đó từ vị trí kí tự đó trong xâu tìm các kí tự tiếp theo, nếu có nhiều kí tự nhỏ nhất thì ta chọn kí tự xuất hiện đầu tiên (để có thêm nhiều lựa chọn cho các kí tự sau)
CÁCH LÀM:
\(1.\) ta cho i chạy từ 1 đến K (để lấy ra K chữ số)
\(2.\) cho j chạy từ \(start\)( \(start\) lúc đầu bằng 0) cho đến \(end\) ( \(end\)lúc đầu bằng \(s.size()-K+1\))
\(3.\) xét trong đoạn này kí tự nhỏ nhất và lưu vào \(min\), mỗi lần xét nếu kí tự bé hơn \(min\) thì đặt \(start=j+1\)
\(4.\) in biến \(min\), tăng biến \(end\) lên 1 đơn vị
\(5.\) lặp lại các bước \(2,3,4\) cho đến khi hết thõa mãn \(1\)
Reference AC CODE||\(O(n)\)time||\(O(|S|)\)space||Xử lý xâu
int main()
{
int k;
cin >> k;
string s;
cin >> s;
int l = s.size() - k + 1;
int r = 0;
for (int i = 1; i <= k;i++) {
int minvl = 10;
int n;
for (int j = r; j < l;j++) {
if (minvl > s[j] - '0') {
minvl = s[j] - '0';
n = j;
}
}
l++;
r = n + 1;
cout << minvl;
}
}
Bình luận