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 
5
1 2 3 4 5
5
1
2
3
4
5
Output 
0
2
4
5
5

Bình luận


  • 0
    ducbao_    8:38 p.m. 28 Tháng 11, 2024
    Hint

    xác định số lượng phần tử tối đa chọn được sao cho trung bình cộng của chúng nhỏ hơn số k[i]


    • 1
      xuankien18062013    8:15 p.m. 28 Tháng 11, 2024
      ( ͡ಠ ʖ̯ ͡ಠ) 
      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)

      • 0
        conganh15112009    11:18 p.m. 29 Tháng 11, 2023

        code bài này tui lm thế này sai chỗ nào v mn

        include <bits/stdc++.h>

        define ll long long

        using namespace std;

        ll n,a[500005],mi[1005],ans=0,s[500005],t,k;

        ll np(ll a[],ll k,ll dau,ll cuoi)
        {
        ll giua;
        while(dau<=cuoi){
        giua=(dau+cuoi)/2;
        if(a[giua]>=giuak)
        cuoi=giua-1;
        if(a[giua]<giua        k)
        dau=giua+1;
        }
        return giua;
        }

        int main()
        {
        cin>>n;
        for(int i=1;i<=n;i++)
        cin>>a[i];
        sort(a+1,a+n+1);
        s[0]=0;
        s[1]=a[1];
        for(int i=2;i<=n;i++)
        s[i]=s[i-1]+a[i];
        cin>>t;
        while(t--){
        cin>>k;
        cout<<np(s,k,0,n)<<"\n";
        }
        }


        • -1
          VoBaThongL921    10:34 p.m. 15 Tháng 11, 2021

          bài ni ko cần chặt nhị phân vẫn ac được 😃


          • 0
            phambinminh12345    2:22 p.m. 17 Tháng 10, 2021

            oi zoi oi


            • -15
              messilionel    8:35 p.m. 10 Tháng 7, 2021

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


              • -22
                messilionel    8:35 p.m. 10 Tháng 7, 2021

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

                1 phản hồi

                • -16
                  messilionel    9:38 a.m. 10 Tháng 7, 2021

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

                  1 phản hồi