首页 > 代码库 > bjfu1208 中位数
bjfu1208 中位数
题目是给你一个数x以及一个长度为n的数列，让你往数列里插入y个数，使数列的中位数正好是x，求y的最小值。(其实这题的中位数跟数学里的中位数有一点区别，略去不提)
那么就排完序以后分情况讨论一下就好了。
具体公式我就不推了，很简单的。这里附上几组我推公式时用到的测试数据(每组三行，前两行是题目的输入，第三行表示添加方法，x表示添加的数)
5 61 2 2 4 51 2 2 4 5 6 x x x x x5 51 2 2 4 51 2 2 4 5 x x x x5 51 2 2 5 51 2 2 5 5 x x5 41 2 2 4 51 2 2 4 5 x x5 31 2 2 4 51 2 2 3 4 5 x5 21 2 2 4 51 2 2 4 59 21 2 2 4 5 6 7 8 9x x x 1 2 2 4 5 6 7 8 95 11 2 2 4 5x x x 1 2 2 4 5
代码如下：
/* * Author : ben */#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <ctime>#include <iostream>#include <algorithm>#include <queue>#include <set>#include <map>#include <stack>#include <string>#include <vector>#include <deque>#include <list>#include <functional>#include <numeric>#include <cctype>using namespace std;#ifdef ON_LOCAL_DEBUG#else#endifconst int maxn = 505;int data[maxn], n, x;int ans;void work() { int mid = (n - 1) / 2; if (data[mid] == x) { return ; } int lb = lower_bound(data, data + n, x) - data; int ub = upper_bound(data, data + n, x) - data - 1; if (ub < mid) { ans += n - 2 * ub - 2; } else { ans += 2 * lb - n + 1; }}int main() {#ifdef ON_LOCAL_DEBUG freopen("data.in", "r", stdin);#endif while (scanf("%d%d", &n, &x) == 2) { ans = 0; bool has = false; for (int i = 0; i < n; i++) { scanf("%d", &data[i]); has = has || (data[i] == x); } if (!has) { data[n++] = x; ans++; } sort(data, data + n); work(); printf("%d\n", ans); } return 0;}
bjfu1208 中位数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。