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, 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
bài này dùng kỹ thuật hay thuật toán gì vậy mọi người, có thể nói để em học thêm được không ạ?
include <bits/stdc++.h>
using namespace std; long long n = 0; long long c = 0; long long a[10000005], b[10000005]; map <long long, long long>m; int main() { iosbase::syncwith_stdio(0); cin.tie(0); cout.tie(0); cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; b[i] = a[i]; } sort(b + 1, b + n + 1); m[b[1]] = 0; for (int i = 2; i <= n; i++) { if (b[i] != b[i - 1]) { m[b[i]] = i - 1; } } for (int i = 1; i <= n; i++) { cout << m[a[i]] << " "; } }