Trung vị

Đề bài

Mô tả

Trung vị của một dãy gồm n phần tử là phần tử đứng ở vị trí (n+1)/2 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ừ 1). Ví dụ, trung vị của dãy (2,6,1,2,3)2, còn trung vị của dãy (0,96,17,23)17.

Cho một dãy gồm n số nguyên và một giá trị x. 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ừ 1 đến 105 (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 x.

Dữ liệu vào

  • Dòng đầu chứa hai số nguyên nx.
  • Dòng thứ hai chứa n 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 x.

Ràng buộc

  • 1n500
  • 1x105
  • Các phần tử của dãy ban đầu là số nguyên trong đoạn từ 1 đến 105.

Ví dụ

Input Output Giải thích
3 10
10 20 30
1 Thêm số 10 vào dãy được (10,10,20,30), trung vị ở vị trí 5/2=210.
3 4
1 2 3
4 Thêm 4,5,5,5 được dãy có trung vị bằng 4.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.46 awk 1.3.4 gcc 16.1.0 csc 6.12.0.200 g++ 16.1.0 g++-themis 16.1.0 g++17 16.1.0 g++20 16.1.0 g++23 16.1.0 clang++ 22.1.6 dmd 2.112.0 dart 3.12.1 gforth 0.7.3 gfortran 12.2.0 go 1.26.3 groovyc 5.0.6 javac 25.0.3 node 26.2.0 kotlinc 2.3.21 sbcl 2.2.9 lua 5.4.8 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.6 pike 8.0 pypy3 7.3.23 python3 3.14.5 racket 8.7 ruby 4.0.5 rustc 1.96.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 tclsh 8.6 bun 1.3.14 deno 2.8.1 v 0.5.1 zig 0.16.0