MEDIAN2
Cho số nguyên \(n\) lẻ và dãy số nguyên \(a_1, a_2, …., a_n.\) Bạn có thể thực hiện thao tác sau với mảng: Chọn một phần tử \(a_i\) và tăng phần tử đó lên một giá trị (\(a_i = a_i +1\) ).
Trung vị của mảng có kích thước lẻ là phần tử ở chính giữa sau khi mảng được sắp xếp theo thứ tự không giảm.
Ví dụ, trung vị của mảng 6 7 5 4 2 9 4 là 5.
Yêu cầu: cần làm cho giá trị trung vị của mảng lớn nhất có thể bằng cách sử dụng tối đa \(k\) thao tác.
Dữ liệu:
Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\) (\(n<=10^6\));
Dòng thứ hai chứa n số nguyên a1, a2, …., a[n];
Kết quả:
- Đưa ra một số nguyên duy nhất - giá trị trung vị lớn nhất có thể có sau khi thực hiện \(k\) thao tác.
Sample Input
3 2
1 3 5
Sample Output
5
Sample Input
5 5
1 2 1 1 1
Sample Output
3
Sample Input
7 7
4 1 2 4 3 4 4
Sample Output
5
Comments