Trung vị mong muốn
Đề bài
Mô tả
Cho một mảng gồm số nguyên và một số nguyên . Đảm bảo rằng là số lẻ.
Trong một thao tác, bạn được chọn đúng một phần tử của mảng và tăng hoặc giảm nó đi . Hãy tính số thao tác ít nhất cần thực hiện để trung vị của mảng bằng .
Trung vị của một mảng có độ dài lẻ là giá trị nằm ở vị trí chính giữa sau khi mảng được sắp xếp tăng dần. Chẳng hạn, trung vị của mảng bằng , vì sau khi sắp xếp ta được và nằm ở vị trí chính giữa.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên và : độ dài mảng và giá trị trung vị mong muốn.
- Dòng thứ hai chứa số nguyên : các phần tử của mảng.
Dữ liệu ra
In ra một số nguyên duy nhất: số thao tác ít nhất để trung vị của mảng bằng .
Ràng buộc
- , lẻ
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 8 6 5 8 |
2 | Tăng lên hai lần, mảng trở thành . Sau khi sắp xếp ta được nên trung vị bằng . |
| 7 20 21 15 12 11 20 19 12 |
6 | Tăng lên một lần và tăng lên năm lần, mảng trở thành . Sau khi sắp xếp ta được nên trung vị bằng . |
Bình luận