Bình luận

• 
  

  5

  SPyofgame    8:05 a.m. 19 Tháng 6, 2020 ← đã chỉnh sửa →

  ---

  Spoiler Alert

  ---

  Hint 1

  • Chỉ thứ tự các chữ số trong \(B\) không thay đổi trong \(C\)

  Đọc kĩ đề nhé mấy bạn, số \(A\) mình có thể thay đổi vị trí bất kì đó

  Ta sẽ tìm cách sắp xếp các chữ số \(A\) trong \(C\) sao cho phù hợp

  ---

  Hint 2

  • Xét bài toán con: Giả sử mình đã có một cách sắp xếp các chữ số trong \(A\) phù hợp, và mình ghép tất cả chữ số của \(A\) và \(B\) vào nhau sao cho nó lớn nhất

  Mình sẽ dùng kĩ thuật \(two-pointers\) để di chuyển 2 con trỏ \(ptr_A\) và \(ptr_B\) sang tới vị trí cuối cùng của 2 số và xuất ra sao cho tối ưu nhất

  Khi này, mình có 2 hướng đi

  Nếu \(ptr_A\) chưa ở cuối \(A\): xuất \(A[ptr_A]\) và di chuyển \(ptr_A\) sang phải

  Nếu \(ptr_B\) chưa ở cuối \(B\): xuất \(B[ptr_B]\) và di chuyển \(ptr_B\) sang phải

  ---

  Hint 3

  • Trong bài toán con trên: Ta sẽ ưu tiên chữ số lớn hơn được xuất trước

  Nếu mình được chọn một trong hai số \(A[ptr_A]\) và \(B[ptr_B]\) để xuất ra số lớn nhất.

  Mà chữ số được xuất trước lớn hơn thì cả số đó sẽ lớn hơn.

  Nên mình sẽ xuất \(max(A[ptr_A], B[ptr_B])\) và di chuyển con trỏ có giá trị \(max\) sang phải

  Và cũng từ đây mình rút ra: \(A\) càng lớn thì số được xuất ra càng lớn.

  Vậy ta sẽ sắp xếp các chữ số trong \(A\) giảm dần

  ---

  Hint 4

  • Trường hợp còn lại cũng tương tự cho đến khi bạn nhận ra \(C\) không chứa các số \(0\) vô nghĩa ở đầu

  Sau khi sắp xếp \(A\) nhỏ dần, ta có thể cho một trong 2 số sau lên đầu số \(C\)

  Chữ số đầu tiên nhỏ nhất khác \(0\) của \(A\)

  Chữ số đầu tiên của \(B\) (phải khác \(0\) và không được chọn vị trí khác)

  Vậy chữ số nào bé hơn và khác \(0\) thì ta sẽ chọn

  Mà chữ số đầu của \(C\) theo cách chọn tối ưu trên sẽ không phụ thuộc cách sắp xếp \(A\)

  Nên ta có swap vị trí chữ số bé nhất khác \(0\) của \(A\) lên đầu khi nó bé hơn chữ số đầu của \(B\)

  ---

  Reference AC code | \(O(n \log_2 n)\) time | \(O(n)\) auxiliary space | Two-pointers, String

  C++

  int main()
  {
      string s; /// so A bieu dien kieu string
      cin >> s;
  
      string t; /// so B bieu dien kieu string
      cin >> t;
  
      sort(all(s)); /// sap xep giam dan
      if (s.front() == '0') /// chu so dau A la so 0
      {
          for (char &c : s) /// tim trong A phan tu dau khac 0
          {
              if (c != '0') /// da tim ra phan tu do
              {
                  if (c < t.front()) /// kiem tra xem no co nho hon chu so dau cua B khong
                  {
                      swap(c, s.front()); /// neu co thi swap len A
                      break;              /// ta khong can tim them nua
                  }
              }
          }
      }
  
      int n = s.size(), m = t.size();
      for (int ps = 0, pt = 0; ps < n && pt < m; ) /// 2 con tro ps, pt
      {
          if (s[ps] < t[pt] && (ps != 0 || pt != 0 || s[ps] != '0')) /// loai bo phan tu leading_zero
               cout << s[ps++]; /// Xuat s[ps] va di chuyen con tro sang phai
          else cout << t[pt++]; /// Xuat t[pt] va di chuyen con tro sang phai  
          if (pt == m) while (ps < n) cout << s[ps++]; /// Da in het B, nen xuat het A
          if (ps == n) while (pt < m) cout << t[pt++]; /// Da in het A, nen xuat het B
      }
      cout << eol;
  
      sort(all(s), greater<char>()); /// sap xep tang dan
      for (int ps = 0, pt = 0; ps < n && pt < m; ) /// 2 con tro ps, pt
      {
          if (s[ps] > t[pt]) /// chon phan tu co gia tri lon hon
               cout << s[ps++]; /// Xuat s[ps] va di chuyen con tro sang phai
          else cout << t[pt++]; /// Xuat t[pt] va di chuyen con tro sang phai  
          if (pt == m) while (ps < n) cout << s[ps++]; /// Da in het B, nen xuat het A
          if (ps == n) while (pt < m) cout << t[pt++]; /// Da in het A, nen xuat het B
      }
      return 0;
  }
  

• 
  

  0

  huanhoang2004    2:50 p.m. 19 Tháng 6, 2020

  tại sao lại không có trường hợp xét \(\(a[i] == b[i]\)\) thì xử lí sao vậy bạn?

• 
  

  1

  SPyofgame    2:59 p.m. 19 Tháng 6, 2020

  Trường hợp đó bạn xuất bên nào chả được :V

• 
  

  1

  minhtuanitk20    10:26 p.m. 6 Tháng 2, 2022

  vd mà trường hợp val(B.front) == val(A.front) thì swap có ảnh hưởng tới vị trí của B ko

• 
  

  0

  nguyendanghau2006    2:44 p.m. 7 Tháng 2, 2022

  ko nhá .-.
4 bình luận nữa