Lại là Trinh thám
Amas là một sinh viên mới vào học tại ĐHGVTVT năm thứ nhất. Kết thúc học kỳ 1, Amas được tham gia một học kỳ quân sự. Hôm nay, lớp học của Amas được chia làm 2 phía chiến trường và tổ chức tập trận, Amas tham gia bên phía quân xanh có nhiệm vụ đi trinh thám quân đỏ huấn luyện. Amas leo lên một quả đồi và sử dụng ống nhòm để quan sát thì phát hiện ra quân đỏ đang dàn hàng ngang để tập luyện, khổ nỗi ống nhòm nhỏ nên mỗi khung nhìn chỉ quan sát được một số lính liên tiếp của quân đỏ. Nhiệm vụ trinh thám lần này là tìm ra chiều cao cao nhất của đối phương, để làm được điều đó rất khó nên phải quan sát dần dần lần lượt từ đầu đến cuối của hàng bằng cách dịch khung nhìn lần lượt mỗi lần tịnh tiến lên một đơn vị.
Bài toán đặt ra với Amas là với n quân đỏ có chiều lượt là \(a_1, a_2...a_n\), khung nhìn có khoảng rộng là \(1<=k<=n\). Khi dịch khung nhìn lần lượt từ đầu đến cuối thì với từng vị trí khung nhìn phải tìm ra chiều cao của quân đỏ cao nhất trong khung nhìn đó
Input
Dòng đầu chứa 2 số n là số quân đỏ \((1<= n <=10^6)\) và k là khung nhìn của ống nhòm \((1<=k<=n)\) (số quân đỏ tối đa mà một lần ống nhòm quan sát được)
Dòng thứ 2 chứa n số nguyên là chiều cao của quân đỏ theo đơn vị chiều cao \((1<= a_i <= 10^6)\)
Output
Kết quả đầu ra gồm n-k+1 số nguyên là chiều cao của quân đỏ cao nhất trong từng khung nhìn
Ví dụ
8 3
4 7 2 5 6 3 9 1Output
7 7 6 6 9 9Giải thích Lần lượt khung nhìn duyệt qua 3 phần tử một tìm \(max(4,7,2), max(7,2,5), max(2,5,6), max(5,6,3), max(6,3,9), max(3,9,1)\)
Comments
Để giảm O(nlogn) chỉ có cách bổ sung thêm mảng đánh dấu vs lazy remove khỏi priority_queue =)))
easy problem with priority_queue
ngon
Em bị TLE test 4,buồn quá :((
Nay mình sinh test cẩn thận tóm ngay được Duy Anh
Quá chặt và không thể áp dụng được thuật giải O(nlogn)