题目描述

难度分:$1500$

输入$n(1 \leq n \leq 500)$，$x(1 \leq x \leq 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq 10^5)$。

向$a$中添加尽量少的数，使得$a$的中位数恰好等于$x$。输出添加的元素个数。

注：如果$n$是偶数，中位数取正中间左边那个。例如$a=[1,3,5,7]$的中位数是$3$。

输入样例$1$

3 10
10 20 30

输出样例$1$

1

输入样例$2$

3 4
1 2 3

输出样例$2$

4

算法

二分答案

写复杂了，做的时候忘记考虑$1 \leq n \leq 500$（也不知道怎么有效利用这个条件）。想着能不能通过分情况讨论做到$O(1)$，但是一直WA，所以最后写了个很复杂的二分。

先对$a$排序，得到数组中小于$x$的数字个数$lt\_cnt$，大于$x$的数字个数$gt\_cnt$，以及等于$x$的数字个数$cnt$。如果$a$中根本就没有$x$，先令数组$a$中大于等于$x$的数字个数为$geq\_cnt=gt\_cnt+cnt$，分为以下三种情况：

1. 如果$lt\_cnt \lt geq\_cnt$，只需要补一个$x$，然后补上$geq\_cnt-lt\_cnt-1$个小于$x$的数即可。
2. 如果$lt\_cnt \gt geq\_cnt$，那就需要补一个$x$，然后补大于等于$x$的元素使数组长度为$2lt\_cnt+1$，一共补了$2lt\_cnt+1-n$个数。
3. 如果$lt\_cnt = geq\_cnt$，只要补一个$x$就行。

否则$a$中有$x$，中位数的位置为$pivot=\lceil \frac{n}{2} \rceil$，其中$\lceil . \rceil$表示对$.$向上取整。分为以下三种情况：

1. $pivot \in [j,k)$，其中$j$是第一个大于等于$x$的位置，$k$是第一个严格大于$x$的位置。此时$x$就是原数组$a$的中位数，不用添加任何其他元素。
2. $pivot \lt j$，大于等于$x$的数少了，有两种方案：添加大于$x$的数、添加等于$x$的数。通过二分来确定最少添加多少个，如果添加$mid$个，目的就是让$lt\_cnt \lt \lceil \frac{n+mid}{2} \rceil$且$lt\_cnt+cnt \geq \lceil \frac{n+mid}{2} \rceil$。意思就是小于$x$的数不能触碰到中位数的位置，同时等于$x$的数要覆盖住中位数的位置。
3. $pivot \geq k$，小于等于$x$的数少了，有两种方案：添加小于$x$的数、添加等于$x$的数。还是对这两种情况分别做二分答案，看哪种添加的数更少。

复杂度分析

时间复杂度

先对$a$数组进行了排序，在最差情况下还要对$a$数组进行两次二分答案，时间复杂度为$O(log_2n)$。因此，整个算法的时间瓶颈在于排序，时间复杂度为$O(nlog_2n)$。

空间复杂度

只使用了有限几个变量，额外空间复杂度为$O(1)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 501;
int n, x, a[N];

int main() {
    scanf("%d%d", &n, &x);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    sort(a + 1, a + n + 1);
    int j = lower_bound(a + 1, a + n + 1, x) - a;
    int k = upper_bound(a + 1, a + n + 1, x) - a;
    if(j <= n) {
        int cnt = k - j;
        int lt_cnt = j - 1;          // 小于x的个数
        int gt_cnt = n - k + 1;      // 大于x的个数
        int geq_cnt = cnt + gt_cnt;
        if(a[j] == x) {
            // 数组a中有x这个数
            int pivot = n + 1 >> 1;
            if(j <= pivot && pivot < k) {
                puts("0");
            }else {
                if(pivot < j) {
                    int l = 1, r = n;
                    // 加大于x的数
                    while(l < r) {
                        int mid = l + r >> 1;
                        if(lt_cnt + cnt >= (n + mid + 1) / 2) {
                            if(lt_cnt < (n + mid + 1) / 2) {
                                r = mid;
                            }else {
                                l = mid + 1;
                            }
                        }else {
                            l = mid + 1;
                        }
                    }
                    int t = r;
                    // 加等于x的数
                    l = 1, r = n;
                    while(l < r) {
                        int mid = l + r >> 1;
                        if(lt_cnt + cnt + mid >= (n + mid + 1) / 2) {
                            if(lt_cnt < (n + mid + 1) / 2) {
                                r = mid;
                            }else {
                                l = mid + 1;
                            }
                        }else {
                            l = mid + 1;
                        }
                    }
                    t = min(r, t);
                    printf("%d\n", t);
                }else {
                    // 加等于x的数
                    int l = 1, r = n;
                    while(l < r) {
                        int mid = l + r >> 1;
                        if(lt_cnt + mid + cnt >= (n + mid + 1)/2) {
                            if(lt_cnt < (n + mid + 1) / 2) {
                                r = mid;
                            }else {
                                l = mid + 1;
                            }
                        }else {
                            l = mid + 1;
                        }
                    }
                    // 加小于x的数
                    int t = r;
                    l = 1, r = n;
                    while(l < r) {
                        int mid = l + r >> 1;
                        if(lt_cnt + mid + cnt >= (n + mid + 1)/2) {
                            if(lt_cnt + mid < (n + mid + 1) / 2) {
                                r = mid;
                            }else {
                                l = mid + 1;
                            }
                        }else {
                            l = mid + 1;
                        }
                    }
                    t = min(t, r);
                    printf("%d\n", t);
                }
            }
        }else {
            // 数组中没有x这个数
            if(geq_cnt > lt_cnt) {
                printf("%d\n", geq_cnt - lt_cnt);
            }else if(geq_cnt < lt_cnt) {
                printf("%d\n", lt_cnt*2 + 1 - n);
            }else {
                puts("1");
            }
        }
    }else {
        // 数组a中全是小于x的数
        printf("%d\n", n + 1);
    }
    return 0;
}