Khai Trương Bīngqílín
Xem dạng PDF
Bedao chuẩn bị khai trương một cửa hàng bán kem! Mọi thứ đã chuẩn bị gần như là đầy đủ: từ địa điểm bán hàng, cho đến menu các loại kem của cửa hàng. Loại kem đặc sắc nhất của Bedao ư? Các bạn hãy xem bài B nhé!
Bây giờ còn một khâu duy nhất trước khi khai trương, đó là treo biển. Biển được treo trước hàng rào của cửa hàng. Hàng rào của cửa hàng tuy thô sơ nhưng mà đơn giản, đời thường, bao gồm ~n~ tấm ván dọc được xếp liên tiếp nhau. Tấm ván thứ ~i~ từ trái sang có độ cao là ~h_i~ dm, và có chiều rộng ~1~ dm.
Biển của cửa hàng Bedao rất rộng, có độ dài đúng bằng ~n~ dm. Để treo biển, Bedao cần chọn ra một chiều cao là ~g~ dm, với ~g~ là số nguyên. Sau đó tại mỗi tấm ván không thấp hơn ~g~ dm, Bedao sẽ đóng một chiếc đinh vào tấm ván này tại vị trí ~g~. Cuối cùng biển sẽ được treo lên tại những chiếc đinh đã đóng.
Bedao được biết rằng, để hàng rào vẫn giữ được tính kiên cố, Bedao không được phép đóng đinh lên quá ~k~ tấm ván. Nhưng Bedao cũng không được cao lắm, do đó Bedao muốn treo biến càng thấp càng tốt.
Cho danh sách độ cao của những tấm ván và số ~k~, hãy giúp Bedao xác định chiều cao ~g~ thấp nhất để treo biển sao cho Bedao không phải đóng đinh quá ~k~ tấm ván, hoặc chỉ ra rằng không tồn tại cách đóng đinh nào thỏa mãn.
Input
Dòng đầu tiên gồm số ~t~ (~1 \le t \le 10\,000~) – số lượng test case trong input. Tiếp đó là mô tả của ~t~ test case.
Dòng đầu tiên của test case của ~t~ test case chứa hai số nguyên ~n~ và ~k~ (~1 \le k \le n \le 100\,000~) – số lượng tấm ván trên hàng rào và số lượng tấm ván tối đa được phép đóng đinh lên.
Dòng tiếp theo của test case chứa ~n~ số nguyên ~h_1, h_2, \ldots, h_n~ (~1 \le h_i \le 10^9~) – chiều cao của các tâm ván theo đơn vị decimet.
Dữ liệu đảm bảo tổng ~n~ của tất cả các test case trong một file input không vượt quá ~10^5~.
Output
Với mỗi test case, hãy in ra độ cao ~g~ (~\displaystyle 1 \le g \le \max_{1 \le i \le n} {a_i}~, ~g~ là số nguyên) thấp nhất để treo biển sao cho Bedao không phải đóng đinh quá ~k~ tấm ván, hoặc in ra ~-1~ nếu như không có cách đóng đinh nào thỏa mãn.
Scoring
Subtask 1 (~100~ điểm): ~h_i \le 30~.
Subtask 2 (~200~ điểm): không có ràng buộc gì thêm.
Tổng cộng bài toán có ~300~ điểm.
Sample Input
3
3 3
3 2 3
3 2
3 2 3
3 1
3 2 3
Sample Output
1
3
-1
Notes
Trong cả ba ví dụ, các tấm ván có độ cao là ~[3, 2, 3]~.
Trong ví dụ đầu tiên, ~k = 3~, tức Bedao được phép đóng đinh ở tất cả các tấm ván. Ví vậy Bedao có thể chọn độ cao là ~1~.
Trong ví dụ thứ hai, ~k = 2~, tức Bedao chỉ được phép đóng đinh vào tối đa hai tấm ván. Có thể thấy rằng nếu chọn ~g = 1~ hoặc ~g = 2~ thì Bedao đều phải đóng cả ba tấm ván, do đó Bedao nên chọn ~g = 3~.
Trong ví dụ thứ ba, ~k = 1~, tức Bedao chỉ được phép đóng đinh vào tối đa một tấm ván. Dù chọn ~g = 1~, ~g = 2~ hay ~g = 3~ thì Bedao đều phải đóng vào ít nhất là hai tấm ván, do đó không có cách đóng đinh nào thỏa mãn trong trường hợp này.
Bình luận
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
chặt nhị phân hoặc đếm phân phối
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.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Này ông, tôi không biết mọi người thấy meme này như thế nào, nhưng đối với tôi, nó tuyệt lắm, cơ mà có vẻ như nó không đáp ứng được tiêu chí là một món ăn tinh thần cho anh em trong group và cả tôi, tôi chắc chắn rằng ông có thể tạo ra những meme còn tuyệt hơn như thế này nhiều, tôi và cả anh em trong group cảm thấy thật hạnh phúc khi có ông trong group, chúng tôi tự hào và xúc động về những cố gắng ông đã đóng góp để phát triển group của chúng ta, tôi thật may mắn vì đã gặp được ông, chào ông và thân ái
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.