Bài tập  /  Bài đang cần trả lời

Cho dãy số nguyên gồm N phần tử

Cho dãy số nguyên gồm N phần tử a1,a2,⋯,aN (|ai|≤10^9). Cho giá trị x và q câu hỏi có dạng S(u,v). Với S(u,v) là tổng các giá trị của các phần tử từ � đến �.

Yêu cầu: Đếm xem trong q câu hỏi đó có bao câu hỏi có giá trị nhỏ hơn x.
Tổng dãy con - LQDOJ: Le Quy Don Online Judge

1 trả lời
Hỏi chi tiết
198
Tham khảo câu trả lời từ Trợ lý ảo Lazi
Để giải bài toán này, ta có thể sử dụng kỹ thuật prefix sum để tính tổng các phần tử từ vị trí 1 đến vị trí i trong dãy số ban đầu. Sau đó, ta sẽ duyệt qua từng câu hỏi và tính tổng của dãy con từ vị trí u đến vị trí v bằng cách lấy tổng tại vị trí v trừ đi tổng tại vị trí u-1. Nếu tổng này nhỏ hơn x, ta tăng biến đếm lên 1.

Dưới đây là mã giả của thuật toán:

1. Đọc vào số phần tử của dãy số N.
2. Đọc vào dãy số a.
3. Tính prefix sum của dãy số a.
4. Đọc vào số câu hỏi q.
5. Với mỗi câu hỏi:
- Đọc vào vị trí u và v.
- Tính tổng của dãy con từ vị trí u đến v bằng cách lấy tổng tại vị trí v trừ đi tổng tại vị trí u-1.
- Nếu tổng này nhỏ hơn x, tăng biến đếm lên 1.
6. In ra giá trị của biến đếm.

Độ phức tạp của thuật toán này là O(N + q), với N là số phần tử của dãy số và q là số câu hỏi.
0
0
Manh Nguyen
31/07/2023 02:08:09

def count_questions(a, x, q):

  """

  Đếm số câu hỏi có giá trị nhỏ hơn x.

 

  Args:

    a: Dãy số nguyên.

    x: Giá trị cần so sánh.

    q: Số câu hỏi.

 

  Returns:

    Số câu hỏi có giá trị nhỏ hơn x.

  """

 

  # Tạo cây nhị phân với các nút là các phần tử của dãy số.

  tree = []

  for i in range(len(a)):

    tree.append(i)

 

  # Gán giá trị của mỗi nút là tổng các giá trị của các phần tử trong cây con bên trái và cây con bên phải của nó.

  for i in range(len(tree) - 1, 0, -1):

    tree[i - 1].sum = tree[i].sum + tree[i + 1].sum + a[i]

 

  # Duyệt qua cây nhị phân từ trên xuống và đếm xem có bao nhiêu nút có giá trị nhỏ hơn x.

  count = 0

  for i in range(len(tree)):

    if tree[i].sum < x:

      count += 1

 

  return count

Mở khóa để xem toàn bộ nội dung trả lời

(?)
Bạn đã đạt đến giới hạn của mình. Bằng cách Đăng ký tài khoản, bạn có thể xem toàn bộ nội dung trả lời
Cải thiện điểm số của bạn bằng cách đăng ký tài khoản Lazi.
Xem toàn bộ các câu trả lời, chat trực tiếp 1:1 với đội ngũ Gia sư Lazi bằng cách Đăng nhập tài khoản ngay bây giờ
Tôi đã có tài khoản? Đăng nhập

Bạn hỏi - Lazi trả lời

Bạn muốn biết điều gì?

GỬI CÂU HỎI
Học tập không giới hạn cùng học sinh cả nước và AI, sôi động, tích cực, trải nghiệm
Bài tập Lập trình Lớp 6 mới nhất
Trắc nghiệm Lập trình Lớp 6 mới nhất

Hôm nay bạn thế nào? Hãy nhấp vào một lựa chọn, nếu may mắn bạn sẽ được tặng 50.000 xu từ Lazi

Vui Buồn Bình thường

Học ngoại ngữ với Flashcard

×
Trợ lý ảo Trợ lý ảo
×
Đấu trường tri thức | Lazi Quiz Challenge +500K