MINPOS - Vị trí nhỏ nhất
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
Cho dãy số nguyên ~a~ có ~N~ phần tử ~a_1, a_2, ..., a_n~. Và ~q~ truy vấn có dạng:
- ~k~: tìm ~i~ nhỏ nhất sao cho ~a_i~ ≤ ~k~.
Input
- Dòng đầu tiên là số nguyên dương ~N~ (~1 <=N <=10^6~)
- Dòng thứ 2 là ~N~ số nguyên ~a_i (1 \le i \le N, |a_i| \le 10^6)~.
- Dòng thứ 3 là số nguyên dương ~q (1 \le q \le 10^5)~.
- ~q~ dòng tiếp theo, mỗi dòng là 1 số nguyên ~k (|k| \le 10^6)~.
Dữ liệu đảm bảo luôn tồn tại đáp số thoả mãn yêu cầu
Output
- ~q~ dòng: với mỗi dòng là kết quả của truy vấn tương ứng
Sample
Input #1
8
18 15 9 4 -3 2 8 9
4
4
9
15
2
Output #1
4
3
2
5
Hint
50% số test của đề bài có ~N~ ≤ ~1000~ và ~q~ ≤ ~1000~
Problem source: bvquoc
Bình luận
include <bits/stdc++.h>
include <vector>
using namespace std;
int main() { int n; cin>>n; vector<int> a(n); for (int i=0;i<n;i++) cin>>a[i]; int q; cin>>q; while(q--){ int k; cin>>k; int pos=-1; for (int i=0;i<n;i++){ if (a[i]<=k){ pos=i+1; break; } }
}
i