Kaninho và bài toán tìm phần tử gần nhất
Xem PDFHôm qua là bữa kiểm tra kiến thức tổng hợp để chuẩn bị đi thi HSG, vì nhận thấy \(Kaninho\) còn yếu về phần mảng, nên hôm nay bố của \(Kaninho\) quyết định ra một bài toán nhằm củng cố kiến thức cho Kaninho như sau:
Cho mảng \(a\) gồm \(n\) phần tử, và chỉ số của mảng bắt đầu từ \(1\).
Yêu cầu: Với mỗi phần tử \(i\) \((1\le i\le n)\) tìm phần tử \(a[j]\) thoả mãn:
-
\(1\) < \(i\) < \(j\le n\)
-
\(a[i]\) < \(a[j]\)
-
\(j\) - \(i\) là nhỏ nhất.
Nếu không tồn tại \(a[j]\) thoả mãn in ra \(-1\)
Input
-
Dòng thứ nhất chứa số \(t\) \((1\le t\le 10)\) - Thể hiện số lượng testcase
-
\(t\) test tiếp theo, mỗi test có dạng như sau:
-
Dòng thứ nhất chứa số \(n\) \((1\le n\le 10^5)\)
-
Dòng thứ hai chứa \(n\) số nguyên \(a_i\) \((1\le a_i\le 50)\)
Output
- Ứng với mỗi testcase, in ra đáp án cần tìm
Scoring
-
Subtask \(1\) (\(37.5\%\) số điểm): \(1\le n\le 20\).
-
Subtask \(2\) (\(62.5\%\) số điểm): không có điều kiện gì thêm.
Example
Test 1
Input
2
5
2 3 1 9 4
7
5 7 9 3 2 1 4Output
3 9 9 -1 -1
7 9 -1 4 4 4 -1
Bình luận
hmm stack
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
no noooooooooooooooooooooooooooooo
thôi bạn 🙂
chắc chuẩn bị nhiều người từ ac thành tle đây mình đoán vậy =))