Minimum
Xem dạng PDF
Gửi bài giải
Điểm:
20,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch
Cho dãy a gồm n phần tử
Yêu cầu: Xác định giá trị nhỏ nhất trong m phần tử liên tiếp
Input:
- Dòng đầu tiên chứa 2 số nguyên dương n, m ~(n \le 10^{5}, m \le n)~
- Dòng tiếp là dãy a gồm n phân tử ~(a_i \le 10^{9})~
Output:
- Ghi ra các giá trị MIN thu được
##Example
Input:
10 6
16 61 18 55 68 60 57 43 10 37
Output:
16 18 18 10 10
##Scoring
- 20% test: ~n \le 10^{3}~
- 80% test: ~n = 10^{5}~
Bình luận
Skibidi dop dop ya ya
Solution By Shinoz
Hint: Yêu cầu: in ra giá trị nhỏ nhất trong m phân tử liên tiếp trong mảng a có n phân tử
Ta thấy rõ việc trâu với độ phức tạp O(nm) ~> 10^{8}~ (hay 1s), nên thay vì ta for lồng để tìm phân tử nhỏ nhất thì trong mỗi lần ta thêm 1 phân tử vào mảng ta hãy xóa phân tử lúc trước thêm vào mảng đi, cụ thể trên input:
Các cấu hình ta cần quan tâm:
16 61 18 55 68 60........................
......61 18 55 68 60 57..................
............18 55 68 60 57 43............
..................55 68 60 57 43 10......
........................68 60 57 43 10 37
Solution (Only C++) - Sliding Window Algorithm + STL + Online Solving
Nhân tiện vì map và set mặc định của nó luôn được sắp xếp tăng dần nên map.begin() và set.begin() sẽ là MIN
có solution ko ? cko xin zới :D
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
siêng lên :D
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
=)) giới hạn của a[i] đâu
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
dung la Skibidi dop dop ya ya
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
=)))))))))))))