C. Median
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
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.
題目大意：給你一個數n 和一個數k，然後給你一個由n個數組成的數列，先按非遞減序排好，然後讓你判斷這個數列的第 (n + 1) / 2 項是不是k（數列的下標從1開始），如果不是，你要往這個數列中插入m個數使插入後的數列的第（n + m + 1） / 2 項是k ， 輸出m的最小值。
解題思路：先判斷數k是否在原數列中，沒有的話就把數k加入數列，然後原始數列排序，接著找出數k在數列中第一次 first 和最後一次出現的位置second，同時算出 t =（n + 1）/ 2 ，如果 t >= first && t <= second ， 就直接輸出結果；如果 t < first ，則需要在數k的後面添加 大於或等於 k 的數 ；如果 t > second ， 則需要在數k的前面 小於或等於 k 的數。
Ps： 此題用暴力法可能會TLE， 我用的是二分法，只是其中有許多細節需要注意。具體請看代碼：
<SPAN style="FONT-SIZE: 18px">#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std ;
const int MAXN = 1e5 + 5 ;
int vis[MAXN] ;
int s[MAXN] ;
bool cmp(int a , int b)
{
return a < b ;
}
int main()
{
int n , k ;
while (scanf("%d%d" , &n , &k) != EOF)
{
int i ;
int ans = 0 ;
memset(vis , 0 , sizeof(vis)) ;
for(i = 1 ; i <= n ; i ++)
{
scanf("%d" , &s[i]) ;
vis[s[i]] ++ ;
}
if(vis[k] == 0) // 如果數列中沒有k，則加入k
{
vis[k] ++ ;
n ++ ;
s[n] = k ;
ans ++ ;
}
sort(s + 1, s + n + 1, cmp) ; // 因為數列的下標是從1 開始的，
//所以要把 1 ~ n 項排序
int t = (n + 1) >> 1 ;
int first = -1 ;
int second = -1 ;
int j ;
for(j = 1 ; j <= n ; j ++) // 記錄 k 第一次出現的位置和最後一次出現的位置
{
if(k == s[j])
{
if(first == -1)
first = j ;
second = j ;
}
}
if(t >= first && t <= second)
{
printf("%d\n" , ans) ;
}
// 以下是二分過程，是此程序的精華，請仔細理解
else if( t < first)
{
int r = n , l = 1 , mid ;
while(r > l + 1) // 注意跳出條件
{
mid = (r + l) >> 1 ;
int tmp = (mid + n + 1) >> 1 ;
if(first < tmp )
{
r = mid - 1 ;
}
else if(first > tmp)
{
l = mid ;
}
else // 注意相等的情況也要單獨判斷
{
r = mid ;
}
}
if(r == l + 1) // 此處也是必不可少的 ！！
{
if((l + n + 1) >> 1 == first)
{
ans += l ;
}
else
ans += r ;
}
else
ans += r ;
printf("%d\n" , ans) ;
}
// 以下過程道理同上
else
{
int r = n , l = 1 , mid ;
while (r > l + 1)
{
mid = (r + l) >> 1 ;
int tmp = (n + mid + 1) >> 1 ;
if(second + mid < tmp)
{
l = mid + 1;
}
else if(second + mid == tmp)
{
r = mid ;
}
else
{
r = mid - 1 ;
}
}
if(r == l + 1)
{
if((l + n + 1) >> 1 == second + l)
{
ans += l ;
}
else
ans += r ;
}
else
ans += r ;
printf("%d" , ans) ;
}
}
return 0 ;
}
</SPAN>
