trang chủ / đề bài / reachmed

Trung vị mong muốn

Đề bài

Mô tả

Cho một mảng a gồm n số nguyên và một số nguyên s. Đảm bảo rằng n 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 1. 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 s.

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 6,5,8 bằng 6, vì sau khi sắp xếp ta được 5,6,8 và 6 nằm ở vị trí chính giữa.

Dữ liệu vào

  • Dòng đầu tiên chứa hai số nguyên n và s: độ dài mảng và giá trị trung vị mong muốn.
  • Dòng thứ hai chứa n số nguyên a1,a2,…,an: 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 s.

Ràng buộc

  • 1≤n≤2·105−1, n lẻ
  • 1≤s≤109
  • 1≤ai≤109

Ví dụ

Input Output Giải thích
3 8
6 5 8
2 Tăng 6 lên hai lần, mảng trở thành 8,5,8. Sau khi sắp xếp ta được 5,8,8 nên trung vị bằng 8.
7 20
21 15 12 11 20 19 12
6 Tăng 19 lên một lần và tăng 15 lên năm lần, mảng trở thành 21,20,12,11,20,20,12. Sau khi sắp xếp ta được 11,12,12,20,20,20,21 nên trung vị bằng 20.

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.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0