Giá trị trung bình

Xem PDF

Tất cả bài nộp

Các bài nộp tốt nhất

Thời gian:

Python 3 10.0s

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

Bạn được một mảng \(A\) gồm \(N\) số nguyên dương.

Bạn sẽ chọn một số phần tử từ mảng \(A\) sao cho giá trị trung bình của các phần tử đã chọn nhỏ hơn \(K\).

Nhiệm vụ của bạn là xác định xem có thể chọn nhiều nhất bao nhiêu phần tử với \(K\) cho trước.

Input

Dòng đâu tiên chứa số nguyên dương \(N\) \((N \leq 5*10^5)\).
Dòng 2 chứa \(N\) số nguyên dương \(A_i\) \((A_i \leq 10^9)\).
Dòng thứ 3 chứa số nguyên \(Q\) \((Q \leq 5\times 10^5)\) - là số câu hỏi.
\(Q\) dòng tiếp theo, mỗi dòng chứa \(1\) giá tri \(K\) \((K \leq 10^9)\).

Output

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

Example

Test 1

Input

Output

Bình luận

( ͡ಠ ʖ̯ ͡ಠ)

def kiemTra(n, pfs, m, k):
if m == 0:
  return True
# Trả lời có chọn được m số trong mảng mà trung bình cộng nhỏ hơn k không.
# Chúng ta kiểm tra nếu trung bình của m phần tử đầu tiên có nhỏ hơn k.
avg = pfs[m] / m  # Trung bình cộng của m số đầu tiên
return avg < k

Nhập 'n' là số lượng phần tử

n = int(input())

Nhập mảng 'arr'

arr = list(map(int, input().split()))

Sắp xếp mảng 'arr'

arr.sort()

Tính prefix sum cho mảng arr

pfs = [0] * (n + 1)
for i in range(1, n + 1):
pfs[i] = pfs[i - 1] + arr[i - 1]

Nhập 'q'

q = int(input())

Trả lời 'q' câu hỏi

for _ in range(q):
k = int(input())

# Sử dụng thuật toán tìm kiếm nhị phân
L, R = 0, n
ans = 0

while L <= R:
    # Ta đoán một giá trị bất 'm'
    M = (L + R) // 2
    # Kiểm tra nếu có thể chọn m phần tử sao cho trung bình < k
    if kiemTra(n, pfs, M, k):
        ans = M  # Lưu lại kết quả và tìm thêm m phần tử lớn hơn
        L = M + 1
    else:
        R = M - 1

print(ans)

7 bình luận nữa