Time Limit: 5 Seconds Memory Limit: 65536 KB
The median of m numbers is after sorting them in order, the middle one number of them if m is even or the average number of the middle 2 numbers if m is odd. You have an empty number list at first. Then you can add or remove some number from the list.
For each add or remove operation, output the median of the number in the list please.
Input
This problem has several test cases. The first line of the input is an integer T (0<T<=100) indicates the number of test cases. The first line of each test case is an integer n (0<n<=10000) indicates the number of operations. Each of the next n lines is either "add x" or "remove x"(-231<=x<231) indicates the operation.
Output
For each operation of one test case: If the operation is add output the median after adding x in a single line. If the operation is remove and the number x is not in the list, output "Wrong!" in a single line. If the operation is remove and the number x is in the list, output the median after deleting x in a single line, however the list is empty output "Empty!".
Sample Input
2 7 remove 1 add 1 add 2 add 1 remove 1 remove 2 remove 1 3 add -2 remove -2 add -1
Sample Output
Wrong! 1 1.5 1 1.5 1 Empty! -2 Empty! -1
Hint
if the result is an integer DO NOT output decimal point. And if the result is a double number , DO NOT output trailing 0s.
题意:
给出 T(0 ~ 100) 组 case,后给出 N(0 ~ 10000) 个操作,有两类操作 “remove” 代表在数列中移除某个数,“add” 代表往数列中添加某个数。每次操作后都输出一个结果,如果删除不存在的数则输出 Wrong!,如果删除后数列为空则输出 Empty!,除此之外都输出这个数列中的中间值。
思路:
STL 中 multiset 的灵活运用,将这个数列分成两半,插入的时候判断第一个数组尾和第二个数组头大小插入,删除时候分别查找两个数组即可。
Multiset 中的元素由小到大自动排列,数列中的数可以重复,而 Set 不可以。
m.erase(a)代表将数组中所有的 a 值删除,m.erase( m.find(a))代表只删除其中一个 a 值,还有 m.end()返回的是数组最末位的下一个位置,要判断最后一个元素的值应该把指针前移一个再做取数的操作。注意这些大概就没有什么问题了。还有数记得要开 long long。
AC:
#include <cstdio> #include <algorithm> #include <cstring> #include <set> #include <cstdlib> using namespace std; typedef long long ll; multiset<ll> m1; multiset<ll> m2; void init() { m1.clear(); m2.clear(); } void Printf() { if (m1.empty() && m2.empty()) puts("Empty!"); else if (m1.size() == m2.size()) { multiset<ll>::iterator it = m1.end(); --it; ll res = *it + *m2.begin(); if (res < 0) { printf("-"); res *= -1; } if (!(res % 2)) printf("%lld\n", res / 2); else printf("%lld.5\n", res / 2); } else printf("%lld\n", *m2.begin()); } void Remove (ll ans) { if (m1.find(ans) == m1.end() && m2.find(ans) == m2.end()) { puts("Wrong!"); return; } else if (m1.find(ans) != m1.end()) { m1.erase( m1.find(ans) ); if (m2.size() - m1.size() == 2) { ll t = *m2.begin(); m1.insert(t); m2.erase( m2.find(t) ); } } else { m2.erase( m2.find(ans) ); if (m1.size() - m2.size() == 1) { multiset<ll>::iterator it = m1.end(); --it; ll t = *it; m2.insert(t); m1.erase( m1.find(t) ); } } Printf(); } void Add (ll ans) { if (m1.empty() && m2.empty()) { m2.insert(ans); } else if (m1.empty() && !m2.empty()) { if (ans > *m2.begin()) { m1.insert( *m2.begin() ); m2.erase( m2.find(*m2.begin()) ); m2.insert(ans); } else m1.insert(ans); } else if (ans >= *m2.begin()){ m2.insert(ans); if (m2.size() - m1.size() == 2) { ll t = *m2.begin(); m2.erase( m2.find(t) ); m1.insert(t); } } else { m1.insert(ans); if (m1.size() - m2.size() == 1) { multiset<ll>::iterator it = m1.end(); --it; ll t = *it; m1.erase( m1.find(t) ); m2.insert(t); } } Printf(); } int main() { //freopen("test.in", "r", stdin); int t; scanf("%d", &t); while (t--) { ll n, ans; char ord[10]; init(); scanf("%lld", &n); while (n--) { scanf("%s%lld", ord, &ans); if (!strcmp(ord, "remove")) Remove(ans); else Add(ans); } } return 0; }
相关推荐
adaptive median algorithm
sci文章 The gravity p-median model
TLD开源代码MedianFlow部分,改造成一个运行程序示例,包含测试主程序及测试视频序列。运行环境:vs2008 + opencv2.4.2
该文件是图像中值滤波和平滑滤波的MATLAB源程序。
中值滤波median_filtermedian_filtermedian_filtermedian_filtermedian_filter
Given an increasing sequence S of N integers, the median is the number at the middle position. For example, the median of S1={11, 12, 13, 14} is 12, and the median of S2={9, 10, 15, 16, 17} is 15. The...
MEDIAN_POLISH Fits an additive model using Tukey s median polish procedure.
this is 3x3 median filter for test.
This document contains a more detailed analysis of the Select or median of medians algorithm than is contained in the text.
A fast median filter using AltiVec,一种有效的中值滤波快速算法。
论文Median filtering in constant time 一文提供的源代码
ZJU考研机试真题 九度1004Median
017_影像平滑(medianBlur、bilateralFilter) _ 阿洲的程式教學1
1.领域:matlab,directional weighted median filter(DWMF)图像的方向加权中值滤波图像去噪 2.内容:directional weighted median filter(DWMF)图像的方向加权中值滤波图像去噪matlab仿真+matlab操作视频 3.用处...
按照多媒体课本上的步骤,严格执行中值区分算法,将24位图像转换为256色图
DBUTM Trimmed Median Filter
自己写的matlab中值滤波程序,简单易懂。滤除噪音,图像模糊
There are two sorted arrays nums1 and nums2 of size m and n respectively. ...Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). Java AC版本
a new directional weighted median filter for removal of random-valued impulse noise,附带matlab代码的
purpose applies median filter to gray-scale PGM image compile gcc -g -o median_pgm median_pgm.c -lpgm -lpbm -lm