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
Bằng cách nhấp vào Đăng nhập, bạn đồng ý Chính sách bảo mật và Điều khoản sử dụng của chúng tôi. Nếu đây không phải máy tính của bạn, để đảm bảo an toàn, hãy sử dụng Cửa sổ riêng tư (Tab ẩn danh) để đăng nhập (New Private Window / New Incognito Window).
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
Tham gia Cộng đồng Lazi trên các mạng xã hội | |
Fanpage: | https://www.fb.com/lazi.vn |
Group: | https://www.fb.com/groups/lazi.vn |
Kênh FB: | https://m.me/j/AbY8WMG2VhCvgIcB |
LaziGo: | https://go.lazi.vn/join/lazigo |
Discord: | https://discord.gg/4vkBe6wJuU |
Youtube: | https://www.youtube.com/@lazi-vn |
Tiktok: | https://www.tiktok.com/@lazi.vn |
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 |