CF166C.Median

普及/提高-

通过率:0%

时间限制:2.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

A median in an array with the length of n is an element which occupies position number after we sort the elements in the non-decreasing order (the array elements are numbered starting with 1). A median of an array (2, 6, 1, 2, 3) is the number 2, and a median of array (0, 96, 17, 23) — the number 17.

We define an expression as the integer part of dividing number a by number b.

One day Vasya showed Petya an array consisting of n integers and suggested finding the array's median. Petya didn't even look at the array and said that it equals x. Petya is a very honest boy, so he decided to add several numbers to the given array so that the median of the resulting array would be equal to x.

Petya can add any integers from 1 to 105 to the array, including the same numbers. Of course, he can add nothing to the array. If a number is added multiple times, then we should consider it the number of times it occurs. It is not allowed to delete of change initial numbers of the array.

While Petya is busy distracting Vasya, your task is to find the minimum number of elements he will need.

长度为 nn 的数组的中位数,是指将数组元素按非递减顺序排序后,位于位置编号为 的元素(数组元素编号从 1 开始)。例如,数组 (2, 6, 1, 2, 3)(2,\,6,\,1,\,2,\,3) 的中位数是 22,而数组 (0, 96, 17, 23)(0,\,96,\,17,\,23) 的中位数是 1717。

我们定义表达式 为整数 aa 除以整数 bb 所得商的整数部分。

一天,Vasya 向 Petya 展示了一个由 nn 个整数组成的数组,并请他找出该数组的中位数。Petya 甚至没有看这个数组,就声称中位数等于 xx。Petya 是一个非常诚实的男孩,因此他决定向给定数组中添加若干个数,使得新数组的中位数恰好等于 xx。

Petya 可以向数组中添加任意在 11 到 10510^5 范围内的整数(包括重复添加相同的数)。当然,他也可以选择不添加任何数。若某个数被多次添加,则在计算时应将其视为相应次数出现。不允许删除或修改原数组中的任何初始元素。

在 Petya 忙着分散 Vasya 注意力的同时,你的任务是求出他所需添加的最少元素个数。

输入格式

The first input line contains two space-separated integers n and x (1 ≤ n ≤ 500, 1 ≤ x ≤ 105) — the initial array's length and the required median's value. The second line contains n space-separated numbers — the initial array. The elements of the array are integers from 1 to 105. The array elements are not necessarily different.

第一行输入包含两个以空格分隔的整数 nn 和 xx(1≤n≤5001 \leq n \leq 500,1≤x≤1051 \leq x \leq 10^5)—— 分别表示初始数组的长度以及目标中位数的值。
第二行包含 nn 个以空格分隔的整数——即初始数组。数组中的元素均为 11 到 10510^5 之间的整数,且元素不一定互不相同。

输出格式

Print the only integer — the minimum number of elements Petya needs to add to the array so that its median equals x.

输出唯一的整数——Petya 需要向数组中添加的最少元素个数,使得其中位数等于 xx。

输入输出样例

  • 输入#1

    3 10
    10 20 30

    输出#1

    1
  • 输入#2

    3 4
    1 2 3

    输出#2

    4

说明/提示

In the first sample we can add number 9 to array (10, 20, 30). The resulting array (9, 10, 20, 30) will have a median in position , that is, 10.

In the second sample you should add numbers 4, 5, 5, 5. The resulting array has median equal to 4.

在第一个样例中,我们可以向数组 (10, 20, 30)(10,\,20,\,30) 中添加数字 99。得到的数组 (9, 10, 20, 30)(9,\,10,\,20,\,30) 的中位数位于位置 ,即为 1010。

在第二个样例中,应添加数字 4, 5, 5, 54,\,5,\,5,\,5。所得数组的中位数等于 44。

输入解题思路,AI测评打分。不知道怎么写?

首页