首页 > 其他 > 详细

Codeforces Round #113 (Div. 2)---C. Median

时间:2015-03-26 23:39:10      阅读:473      评论:0      收藏: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.
Sample test(s)
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.

简单题,分类讨论大法好!

/*************************************************************************
    > File Name: CF-113-C.cpp
    > Author: ALex
    > Mail: zchao1995@gmail.com 
    > Created Time: 2015年03月26日 星期四 18时56分05秒
 ************************************************************************/

#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
const double eps = 1e-15;
typedef long long LL;
typedef pair <int, int> PLL;

int arr[550];

int main()
{
    int n, val;
    while (~scanf("%d%d", &n, &val))
    {
        int sma = 0, equ = 0, big = 0;
        for (int i = 1; i <= n; ++i)
        {
            scanf("%d", &arr[i]);
            if (arr[i] < val)
            {
                ++sma;
            }
            else if (arr[i] == val)
            {
                ++equ;
            }
            else
            {
                ++big;
            }
        }
        if (!equ)
        {
            if (sma < big)
            {
                printf("%d\n", abs(sma - big));
            }
            else
            {
                printf("%d\n", abs(sma - big) + 1);
            }
            continue;
        }
        if (sma >= (n + 1) / 2)
        {
            int ans = 0;
            if ((n + 1) % 2)
            {
                ans += 1 + (sma - (n + 1) / 2) * 2;
            }
            else
            {
                ans += (sma - (n + 1) / 2 + 1) * 2;
            }
            printf("%d\n", ans);
        }
        else if (sma + equ >= (n + 1) / 2)
        {
            printf("0\n");
        }
        else
        {
            int ans = 0;
            if ((n + 1) % 2)
            {
                ans += ((n + 1) / 2 - sma - equ) * 2;
            }
            else
            {
                ans += ((n + 1) / 2 - sma - equ - 1) * 2 + 1;
            }
            printf("%d\n", ans);
        }
    }
    return 0;
}

Codeforces Round #113 (Div. 2)---C. Median

原文:http://blog.csdn.net/guard_mine/article/details/44654593

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!