题目是给你一个数x以及一个长度为n的数列,让你往数列里插入y个数,使数列的中位数正好是x,求y的最小值。(其实这题的中位数跟数学里的中位数有一点区别,略去不提)
那么就排完序以后分情况讨论一下就好了。
具体公式我就不推了,很简单的。这里附上几组我推公式时用到的测试数据(每组三行,前两行是题目的输入,第三行表示添加方法,x表示添加的数)
x x x x x x x x x x x x x x x x x x x x
代码如下:
/*
* 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
#endif
const int maxn = ;
int data[maxn], n, x;
int ans; void work() {
int mid = (n - ) / ;
if (data[mid] == x) {
return ;
}
int lb = lower_bound(data, data + n, x) - data;
int ub = upper_bound(data, data + n, x) - data - ;
if (ub < mid) {
ans += n - * ub - ;
} else {
ans += * lb - n + ;
}
} int main() {
#ifdef ON_LOCAL_DEBUG
freopen("data.in", "r", stdin);
#endif
while (scanf("%d%d", &n, &x) == ) {
ans = ;
bool has = false;
for (int i = ; 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 ;
}
bjfu1208 中位数的更多相关文章
-
[LeetCode] Find Median from Data Stream 找出数据流的中位数
Median is the middle value in an ordered integer list. If the size of the list is even, there is no ...
-
[LeetCode] Median of Two Sorted Arrays 两个有序数组的中位数
There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two ...
-
BZOJ1303 [CQOI2009]中位数图
本文版权归ljh2000和博客园共有,欢迎转载,但须保留此声明,并给出原文链接,谢谢合作. 本文作者:ljh2000 作者博客:http://www.cnblogs.com/ljh2000-jump/ ...
-
在MySQL中,如何计算一组数据的中位数?
要得到一组数据的中位数(例如某个地区或某家公司的收入中位数),我们首先要将这一任务细分为3个小任务: 将数据排序,并给每一行数据给出其在所有数据中的排名. 找出中位数的排名数字. 找出中间排名对应的值 ...
-
AC日记——中位数 洛谷 P1168
题目描述 给出一个长度为N的非负整数序列A[i],对于所有1 ≤ k ≤ (N + 1) / 2,输出A[1], A[2], …, A[2k - 1]的中位数.[color=red]即[/color] ...
-
[2016湖南长沙培训Day4][前鬼后鬼的守护 chen] (动态开点线段树+中位数 or 动规 or 贪心+堆优化)
题目大意 给定一个长度为n的正整数序列,令修改一个数的代价为修改前后两个数的绝对值之差,求用最小代价将序列转换为不减序列. 其中,n满足小于500000,序列中的正整数小于10^9 题解(引自mzx神 ...
-
LeetCode 4 Median of Two Sorted Arrays 查找中位数,排除法,问题拓展 难度:1
思路:设现在可用区间在nums1是[s1,t1),nums2:[s2,t2) 1.当一个数组可用区间为0的时候,由于另一个数组是已经排过序的,所以直接可得 当要取的是最小值或最大值时,也直接可得 2. ...
-
BZOJ 1303 CQOI2009 中位数图 水题
1303: [CQOI2009]中位数图 Time Limit: 1 Sec Memory Limit: 162 MBSubmit: 2340 Solved: 1464[Submit][Statu ...
-
【算法之美】求解两个有序数组的中位数 — leetcode 4. Median of Two Sorted Arrays
一道非常经典的题目,Median of Two Sorted Arrays.(PS:leetcode 我已经做了 190 道,欢迎围观全部题解 https://github.com/hanzichi/ ...
随机推荐
-
[转]搭建Maven私服
在开发过程中,有时候会使用到公司内部的一些开发包,显然把这些包放在外部是不合适的.另外,由于项目一直在开发中,这些内部的依赖可能也在不断的更新.可以通过搭建公司内部的Maven服务器,将第三方和内部的 ...
-
PAT A 1004. Counting Leaves (30)【vector+dfs】
题目链接:https://www.patest.cn/contests/pat-a-practise/1004 大意:输出按层次输出每层无孩子结点的个数 思路:vector存储结点,dfs遍历 #in ...
-
STL中的算法小结
()要运用STL的算法,首先必须包含头文件<algorithm>,某些STL算法用于数值处理,因此被定义于头文件<numeric> ()所有STL算法都被设计用来处理一个或多个 ...
-
css阴影效果
moz-box-shadow: 0 0 10px #888; -webkit-box-shadow: 0 0 10px#888; box-shadow: 0 0 10px #888;
-
Hibernate五 HQL查询
HQL查询一 介绍1.HQL:Hibernate Query Language,是一种完全面向对象的查询语言.使用Hibernate有多重查询方式可供选择:hibernate的HQL查询,也可以使用条 ...
-
iOS实践01
去年放假之前大概完成了新浪微博项目,到现在也忘得差不多了,打算在重新写一遍.之前的一些笔记在新浪的博客SleenXiu,在这主要是把新浪微博以随笔的形式写在这,方便以后的复习. 先看看之前主要完成的几 ...
-
confirm显示数组中的内容时,总是带一个逗号分隔的解决方法
问题的关键 就是在给confirm显示之前,将数组转换成字符串,并以每个数组的元素为一个字符串,加上一个换行回车符即可: 代码中的背景色 为关键的点 <script type="tex ...
-
用css画一个哆啦A梦
原图: 效果图: 虽然说没用啥什么高级的技巧,但这让我感受到了CSS的乐趣! 好好学习,天天向上! <!DOCTYPE html> <html> <head> &l ...
-
WinHex18.4算法分析
经过分析,注册码分为六个部分: Name: "xxx" Addr1: "yyy" Addr2: "zzz" 这三个字符不代表长度 Key1: ...
-
[git] 常用配置
基本配置 对git进行配置时使用 git config 命令进行操作 1. git config 的作用域,缺省等于 local git config --local #只针对某个仓库有效 git ...