Khẩu trang
View as PDF
Points:
200 (p)
Time limit:
1.0s
Memory limit:
1023M
Input:
stdin
Output:
stdout
Khi nghe tin Đà Nẵng có ca dịch Covid mới, Khôi liền chạy tới tiệm thuốc mua khẩu trang.
Cửa hàng có \(n\) hộp khẩu trang. Giá của mỗi hộp khẩu trang được biểu diễn bằng mảng \(A\). Hộp thứ \(i\) có giá \(A_i\) đồng.
Bất chợt có một người đàn ông tên là đến hỏi Khôi vài câu hỏi. Mỗi câu hỏi, Khôi sẽ trả lời số hộp khẩu trang có giá tiền nhỏ hơn \(M\) đồng.
Input
- Dòng đâu tiên chứa số nguyên dương \(N\) \((N \leq 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 10^5)\) - là số câu hỏi.
- \(Q\) dòng tiếp theo, mỗi dòng chứa \(1\) giá tri \(M\) \((M \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 4 10 5 6
4
2
3
5
11Output
1
1
2
5
Comments
số phần tử trong mảng a có đc lặp lại ko?
https://ideone.com/oDaz8S
Hint
Sắp xếp mảng vừa nhập, sử dụng chặt nhị phân tìm phần tử lớn nhất nhỏ hơn M rồi in ra vị trí (có thể sử dụng vector và hàm lower_bound)
ko biết
các cao nhân xem giúp em vs code em ko bik sai chỗ nào:
include<bits/stdc++.h>
using namespace std;
int bi(long long arr[], long long l, long long r, long long x) {
int mid = l+(r-l)/2;
if(r<l){
if(arr[0]<x) return 1;
else return -1;
}
if(arr[mid]<x && arr[mid+1]>=x){
if(arr[1]<x) return mid+1;
else return mid;
}
if (arr[mid] == x) return bi(arr, l, r-1, x);
if (arr[mid] < x) return bi(arr, mid+1,r, x);
return bi(arr, l,mid-1, x);
}
int main(){
long long n,t,k,i,d;
cin>>n;
long long a[n+1];
for(i=1;i<=n;i++) cin>>a[i];
sort(a,a+n);
cin>>t;
while(t--){
cin>>k;
cout<<bi(a,1,n+1,k)<<endl;
}
}
This comment is hidden due to too much negative feedback. Click here to view it.
ai cho biết yêu cầu là gì với ạ
bài này chặt phát ra ngay
code của mình nộp bị lỗi compiler output too long (> 64kb) là sao nhỉ mọi người