maxle

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
PhanDinhKhoi
Dạng bài
Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 1023M Input: bàn phím Output: màn hình

Cho dãy số nguyên \(a\) gồm \(n\) phần tử được sắp xếp tăng dần. Hãy xác định giá trị lớn nhất của \(i\) sao cho \(a_i \le x\). Nếu không có vị trí thõa mãn in ra \(0\).

Input

  • Dòng đâu tiên chứa số hai số nguyên dương \(n\) và \(k\) - độ dài của dãy, số câu hỏi. \((n, k \leq 100000)\)
  • \(n\) số, các phần tử dãy \(a\) \((-10^9 \le a_i \le 10^9)\)
  • \(k\) số nguyên dương \(x\) \((-10^9 \le x \le 10^9)\).

Output

  • Gồm \(k\) dòng, mỗi dòng chứa câu trả lời cho mỗi câu hỏi.

Example

Test 1

Input 
 5 5
 3 3 5 8 9
 2 4 8 1 10
Output 
0
2
4
0
5

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

    • 0
      dackhoatvd2015    6:34 p.m. 4 Tháng 11, 2024 ← đã chỉnh sửa

      bài này hơi khó


      • -3
        hoanganhnguyen    9:31 a.m. 27 Tháng 7, 2024

        em vẫn còn chưa hiểu.Mấy anh giải thích vì sao k :Đ
        em ngu văn lắm nên không biết đọc đề

        1 phản hồi

        • -9
          penistone    2:05 p.m. 13 Tháng 11, 2023

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


          • -6
            thanhphuc_02    5:22 p.m. 12 Tháng 9, 2023

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