Bình luận

• 
  

  1

  Gicungduoc    6:58 p.m. 8 Tháng 11, 2024

  Hint

  Chúng ta sẽ nghĩ đến việc sử dụng tìm kiếm nhị phân.

  Python

  n, k = map(int, input().split())
  
  a = list(map(int, input().split()))
  
  x = list(map(int, input().split()))
  
  for i in x :
      l,r, res = 0, n - 1, 0
      while l <= r :
          m = (l + r) // 2
          if a[m] <= i :
              res = m + 1
              l = m + 1
          else :
              r = m - 1
      print(res)
  

  Giải thích code :

  • Trước tiên, chúng ta sẽ giải thích về thuật toán:

    • Cho một arr được xắp xếp được đánh dấu điểm bắt đầu là L, kết thúc arr là R. Và chúng ta sẽ tìm mid (công tính là (L + R) // 2)
    • Ta có số x cho trước, nếu x <= arr[mid] thì chúng ta sẽ xóa đoạn mid -> R. Hay đặt R lại bằng m - 1. Đặt r đằng trước m. Nên R = m - 1
    • Nếu a[mid] <= x thì chúng ta sẽ xóa đoạn mid -> L. Hay đặt L lại bằng m + 1. Đặt l đằng sau m. Nên L = m + 1

  • Giải thích code mẫu:

    • Nhập dữ liệu vào
    • Đặt biến xử lí
    • Xét từng phần tử của mảng x:
      • Xử lí tìm kiếm nhị phân
      • Nếu a[m] <= x: Đặt biến res = m + 1 (phần tử trong python bắt đầu từ 0)
      • In ra res
4 bình luận nữa