Xâu min

Xem PDF




Thời gian:
Scratch 5.0s
Bộ nhớ:
Scratch 256M

Tác giả:
Dạng bài
Điểm: 1300 (p) Thời gian: 1.0s Bộ nhớ: 64M 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


  • 0
    thanhlong2k9 7:12 p.m. 18 Tháng 3, 2024

    bài này dùng stack vẫn được mà đk mn


    • -3
      tk22NguyenNguyenKhang 9:28 p.m. 19 Tháng 8, 2023

      sao sai vay ban


      • -2
        nguyentheanh2012 9:58 p.m. 11 Tháng 4, 2023

        ngôn ngữ gì vậy N7hoatt

        1 phản hồi

        • -14
          thanhyl7a20 3:51 p.m. 12 Tháng 10, 2021

          Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.


          • -17
            hongquanyl1 3:34 p.m. 22 Tháng 5, 2021

            Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.


            • -21
              nqkts001 9:46 a.m. 22 Tháng 5, 2021

              Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.


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

                1 phản hồi