Trung vị
Đề bài
Mô tả
Trung vị của một dãy gồm phần tử là phần tử đứng ở vị trí sau khi sắp xếp dãy theo thứ tự không giảm (các phần tử được đánh số bắt đầu từ ). Ví dụ, trung vị của dãy là , còn trung vị của dãy là .
Cho một dãy gồm số nguyên và một giá trị . Bạn được phép thêm vào dãy một số phần tử tùy ý, mỗi phần tử là một số nguyên trong đoạn từ đến (có thể thêm các số trùng nhau, hoặc không thêm phần tử nào). Không được xóa hay thay đổi các phần tử ban đầu.
Hãy tìm số lượng phần tử ít nhất cần thêm vào để trung vị của dãy thu được bằng đúng .
Dữ liệu vào
- Dòng đầu chứa hai số nguyên và .
- Dòng thứ hai chứa số nguyên là các phần tử của dãy ban đầu.
Dữ liệu ra
- In ra một số nguyên duy nhất là số phần tử ít nhất cần thêm vào để trung vị của dãy bằng .
Ràng buộc
- Các phần tử của dãy ban đầu là số nguyên trong đoạn từ đến .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 10 10 20 30 |
1 | Thêm số vào dãy được , trung vị ở vị trí là . |
| 3 4 1 2 3 |
4 | Thêm được dãy có trung vị bằng . |
Bình luận