C - Median(166C 思维+ 二分)

刺骨的言语ヽ痛彻心扉 2022-02-19 10:53 179阅读 0赞

### 题目描述： ###

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.

Input  
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.

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

Examples  
Input  
3 10  
10 20 30  
Output  
1  
Input  
3 4  
1 2 3  
Output  
4  
Note  
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.  
题目链接：[http://codeforces.com/problemset/problem/166/C][http_codeforces.com_problemset_problem_166_C]

##### 分析： #####

做这道题的时候， 压根思路就没想好， 只觉得是个水题就敲代码了。  
结果心态就崩了。 所以，做题的时候千万不能太急，一定要把思路想明白！！！不过有多水，一定要想明白。尤其是这种细节超多的题目。  
首先，求中位数需要添加几位数。那么久需要看这个序列里面有没有x，这是两种情况。  
如果有的话，直接用这个数左边的个数和右边的个数相减的绝对值就可以了。 不过还需要注意一点。 如果右边的个数比左边的个数多， 那么你得到的绝对值还需要在减去一。 模拟一下就可得到。

#include"stdio.h"
    #include"string.h"
    #include"algorithm"
    using namespace std;
    int main()
    {
        int n,x;
        int a[510];
        scanf("%d%d",&n,&x);
        for(int i=1; i<=n; i++)
            scanf("%d",&a[i]);
        sort(a+1,a+n+1);
        int pos = lower_bound(a+1,a+n+1,x) - a;
        int ans = upper_bound(a+1,a+n+1,x) - a;
        if(pos > n) { printf("%d\n",n + 1); return 0;}//这两种情况特判
        if(ans == 1) { printf("%d\n",n); return 0;}
        int minx = 99999;
        for(int i = pos; i < ans; i ++)
            {
                int cnt =( n - i ) > (i - 1);
                minx = min((abs((n - i) - (i -1)) - cnt),minx);
            }
        if(minx != 99999) { printf("%d\n",minx); return 0;}
        int cnt = 1;
        pos = ans ;
        n ++;
        int id =(n - pos) > (pos - 1);
        printf("%d\n",abs((n - pos) - (pos - 1)) + cnt - id);
    }

[http_codeforces.com_problemset_problem_166_C]: http://codeforces.com/problemset/problem/166/C