Điểm:
200 (p)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Cho dãy số nguyên dương gồm \(N\) phần tử \(a_1,a_2,...,a_N\). Với mỗi chỉ số \(1 \le i \le N\) đếm xem có bao nhiêu phần tử bé hơn \(a_i\).
Input
- Dòng đầu tiên gồm số nguyên dương \(N\) \((2 \le N \le 10^5)\)
- Dòng thứ hai gồm \(N\) số nguyên dương \(a_1,a_2,...,a_N\) \((a_i \le 10^9)\)
Output
- In ra \(N\) số nguyên, số thứ \(i\) cho biết số phần tử nhỏ hơn \(a_i\).
Scoring
- Subtask \(1\) (\(50\%\) số điểm): \(n \le 10^3\)
- Subtask \(2\) (\(50\%\) số điểm): không ràng buộc gì thêm.
Example
Test 1
Input
5
3 2 1 1 2
Output
4 2 0 0 2
Bình luận
Bài này hay nhất là dùng lower_bound
include <bits/stdc++.h>
using namespace std;
int main(){
int n; cin >> n;
int a[n];
for(int i = 1; i <= n; i++){
cin >> a[i];
}
int sl = 0;
for(int i = 1; i <= n; i++){
int maxn = a[i];
sl = 0;
for(int i = 1; i <= n; i++){
if(a[i] < maxn){
sl++;
}
}
cout << sl << " ";
}
}
hyt
test sai sai
bài này quy hoạch động ac nè
...
Spoiler Alert
Hint 1
Reference 90 score + TLE code | \(O(n ^ 2)\) time | \(O(n)\) query | \(O(1)\) auxiliary space | Brute-force
Hint 2
Hint 3
Hint 4
Reference AC code | \(O(n\) \(log_2 n)\) time | \(O(log_2 n)\) query | \(O(n)\) auxiliary space | Sorting, Binary_search
Reference AC code | \(O(n\) \(log_2 n)\) time | \(O(1)\) query | \(O(n)\) auxiliary space | Sorting, Binary_search
Reference AC code | \(O(n\) \(log_2 n)\) time | \(O(1)\) query | \(O(n)\) auxiliary space | Sorting, Binary_search, STL
Cho em hỏi hình như test 9 và 10 của bài này hình như a[i] có = 0 đúng không ạ? tại em code thôi đề là nguyên dương thì wa 2 test đó còn khi em code có thêm trường hợp ai = 0 thì ac :'(. Không biết có phải là do em code sai không nữa