HEIGHT - Đếm số học sinh thấp hơn
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift
Lớp KC97 tại trường học Free Contest có ~N~ học sinh, các học sinh được đánh số từ ~1~ đến ~N~. Học sinh ~i~ có chiều cao là ~A_i~. Với mỗi học sinh ~i~ từ ~1~ đến ~N~, hãy đếm xem có bao nhiêu học sinh có chiều cao thấp hơn so với học sinh ~i~.
Input
- Dòng đầu tiên gồm số nguyên ~N~ ~(1 ≤ N ≤ 10^5)~ - số học sinh trong lớp;
- Dòng thứ hai gồm một dãy ~N~ số nguyên ~A_1, A_2, ..., A_N~ ~(1 ≤ A_i ≤ 10^9)~ - cho biết chiều cao của các học sinh.
Giới hạn:
- ~50\%~ bộ test: N ≤ 10^3~
- ~50\%~ bộ test: Không có ràng buộc gì thêm
Output
- In ra ~N~ số nguyên, số nguyên thứ ~i~ cho biết số học sinh có chiều cao thấp hơn học sinh ~i~.
Sample
Input #1
4
110 120 130 140
Output #1
0 1 2 3
Hint
- Trong ví dụ trên, có ~2~ học sinh có chiều cao thấp hơn học sinh ~3~ là học sinh ~1~ và họcsinh ~2~.
Problem source: Kc97ble - Free Contest
Bình luận
include <bits/stdc++.h>
define ll long long
using namespace std; ll n, x, a[1000011],b[1000011]; ll Find1(ll a[],ll n,ll x){ ll d=1,c=n,g,res=0; while(d<=c){ g=(d+c)/2; if(a[g]<x){ res=g; d=g+1; }else{ c=g-1; } } return res; } int main() { cin>>n; for(ll i=1;i<=n;i++){ cin>>a[i]; b[i]=a[i]; } sort(b+1,b+n+1); for(ll i=1;i<=n;i++){ cout<<Find1(b,n,a[i])<<" "; } return 0; }
Dùng CTDL map là tốt nhất
bài này dùng CTDL hoặc tknp đều acc nhé