Giá trị trung bình
Xem PDF
Đ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
5Output
0
2
4
5
5
Bình luận
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]<giuak)
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";
}
}
bài ni ko cần chặt nhị phân vẫn ac được 😃
oi zoi oi
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.