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
    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";
    }
    }

      • 7 bình luận nữa