Xâu min

Xem PDF
Thời gian:
Scratch 5.0s
Tác giả:
admin
Dạng bài
Điểm: 1300 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho xâu \(S\) chứa các kí tự \(1 \ldots 9\) (\(|S| \leq 1000\) kí tự) và số nguyên \(K\) (\(1 \leq K \leq |S|\)). (\(|S|\) độ dài của xâu \(S\))

Yêu cầu: Chọn \(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.

Input

  • Dòng 1: Ghi số \(K\).
  • Dòng 2: Ghi xâu \(S\).

Output

  • Ghi một số duy nhất \(X\).

Example

Test 1

Input 
3
89678982
Output 
672

Bình luận


  • 36
    N7hoatt    9:39 p.m. 30 Tháng 7, 2020 ← chỉnh sửa 8

    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;
                            }
                      }


    • 0
      tantaidepzai    7:40 p.m. 22 Tháng 4, 2024

      thank


      • -1
        anhthu030412    5:05 p.m. 17 Tháng 7, 2023

        c++ mấy v b


        • 1
          N7hoatt    5:21 p.m. 17 Tháng 7, 2023

          từ c++ 11 trở lên là được hết bạn nhe

      6 bình luận nữa