无序数组的中位数(set+deque)hdu5249

时间:2022-09-06 22:31:53

KPI

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 901    Accepted Submission(s): 398

Problem Description
你工作以后, KPI 就是你的全部了. 我开发了一个服务,取得了很大的知名度。数十亿的请求被推到一个大管道后同时服务从管头拉取请求。让我们来定义每个请求都有一个重要值。我的KPI是由当前管道内请求的重要值的中间值来计算。现在给你服务记录,有时我想知道当前管道内请求的重要值得中间值。
 
Input
有大约100组数据。

每组数据第一行有一个n(1≤n≤10000),代表服务记录数。

接下来有n行,每一行有3种形式
  "in x": 代表重要值为x(0≤x≤109)的请求被推进管道。
  "out": 代表服务拉取了管道头部的请求。
  "query: 代表我想知道当前管道内请求重要值的中间值. 那就是说,如果当前管道内有m条请求, 我想知道,升序排序后第floor(m/2)+1th 条请求的重要值.

为了让题目简单,所有的x都不同,并且如果管道内没有值,就不会有"out"和"query"操作。

 
Output
对于每组数据,先输出一行

Case #i:
然后每一次"query",输出当前管道内重要值的中间值。

 
Sample Input
6
in 874
query
out
in 24622
in 12194
query
 
Sample Output
Case #1:
874
24622
 

 分析:题目中说有值的加入和值的取出,首先可以用双端队列维护一个队列请求,即先进先出,用q.front()和q.pop_front()读取和删除队列头元素,用q.back()和q.push_back()读取和加入队尾元素,而维护队列的有序可以用set容器,分别建立两个容器sa和sb,无论是删除和加入元素的时候保证size(sa)==size(sb)或者size(sb)+1==size(sb);则sb.begin()  就是中位数的值

程序:

 #include"stdio.h"
#include"string.h"
#include"stdlib.h"
#include"algorithm"
#include"queue"
#include"math.h"
#include"iostream"
#include"vector"
#define M 100009
#define inf 0x3f3f3f3f
#define eps 1e-9
#define PI acos(-1.0)
#include"map"
#include"vector"
#include"set"
#include"string"
using namespace std;
int main()
{
int n,kk=;
while(scanf("%d",&n)!=-)
{
set<int>sa,sb;
sa.insert(-);
sb.insert();
deque<int>q;
printf("Case #%d:\n",kk++);
while(n--)
{
char str[];
scanf("%s",str);
if(strcmp(str,"in")==)
{
int k;
scanf("%d",&k);
q.push_back(k);
sa.insert(k);
int la=sa.size();
int lb=sb.size();
int u=*(sa.rbegin());
int v=*(sb.begin());
if(la>lb)
{
sa.erase(u);
sb.insert(u);
}
u=*(sa.rbegin());
v=*(sb.begin());
if(u>v)
{
sb.erase(v);
sa.insert(v);
sa.erase(u);
sb.insert(u);
}
}
else if(strcmp(str,"out")==)
{ int u=q.front();
q.pop_front();
sa.erase(u);
sb.erase(u); int la=sa.size();
int lb=sb.size();
if(la+==lb)
{
sa.insert(*(sb.begin()));
sb.erase(*(sb.begin()));
}
else if(la==lb+)
{
sb.insert(*(sa.rbegin()));
sa.erase(*(sa.rbegin()));
}
}
else
{
printf("%d\n",*(sb.begin()));
}
}
}
return ;
}
/* 40
in 11
in 22
in 33
in 44
in 55
in 66
query */

无序数组的中位数(set+deque)hdu5249的更多相关文章

  1. 1005E1 Median on Segments &lpar;Permutations Edition&rpar; 【思维&plus;无序数组求中位数】

    题目:戳这里 百度之星初赛原题:戳这里 题意:n个不同的数,求中位数为m的区间有多少个. 解题思路: 此题的中位数就是个数为奇数的数组中,小于m的数和大于m的数一样多,个数为偶数的数组中,小于m的数比 ...

  2. 两个无序数组分别叫A和B,长度分别是m和n,求中位数,要求时间复杂度O&lpar;m&plus;n&rpar;,空间复杂度O&lpar;1&rpar; 。

    #include <iostream> using namespace std; /*函数作用:取待排序序列中low.mid.high三个位置上数据,选取他们中间的那个数据作为枢轴*/ i ...

  3. 从0打卡leetcode之day 5 ---两个排序数组的中位数

    前言 我靠,才坚持了四天,就差点不想坚持了.不行啊,我得把leetcode上的题给刷完,不然怕是不好进入bat的大门. 题目描述 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 . ...

  4. 无序数组求第K大的数

    问题描述 无序数组求第K大的数,其中K从1开始算. 例如:[0,3,1,8,5,2]这个数组,第2大的数是5 OJ可参考:LeetCode_0215_KthLargestElementInAnArra ...

  5. &lbrack;LeetCode&rsqb; 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 ...

  6. 有1,2,3一直到n的无序数组,排序

    题目:有1,2,3,..n 的无序整数数组,求排序算法.要求时间复杂度 O(n), 空间复杂度O(1). 分析:对于一般数组的排序显然 O(n) 是无法完成的. 既然题目这样要求,肯定原先的数组有一定 ...

  7. 快速查找无序数组中的第K大数?

    1.题目分析: 查找无序数组中的第K大数,直观感觉便是先排好序再找到下标为K-1的元素,时间复杂度O(NlgN).在此,我们想探索是否存在时间复杂度 < O(NlgN),而且近似等于O(N)的高 ...

  8. 2&period;Median of Two Sorted Arrays &lpar;两个排序数组的中位数&rpar;

    要求:Median of Two Sorted Arrays (求两个排序数组的中位数) 分析:1. 两个数组含有的数字总数为偶数或奇数两种情况.2. 有数组可能为空. 解决方法: 1.排序法 时间复 ...

  9. 【转载】两个排序数组的中位数 &sol; 第K大元素(Median of Two Sorted Arrays)

    转自 http://blog.csdn.net/zxzxy1988/article/details/8587244 给定两个已经排序好的数组(可能为空),找到两者所有元素中第k大的元素.另外一种更加具 ...

随机推荐

  1. Storm累计求和中使用各种分组Grouping

    Shuffle Grouping: 随机分组, 随机派发stream里面的tuple, 保证bolt中的每个任务接收到的tuple数目相同.(它能实现较好的负载均衡) Fields Grouping: ...

  2. angularjs指令中的compile与link函数详解(转)

    http://www.jb51.net/article/58229.htm 通常大家在使用ng中的指令的时候,用的链接函数最多的是link属性,下面这篇文章将告诉大家complie,pre-link, ...

  3. simhash--文本排重

    转载自 https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/06.12.md http: ...

  4. Docker镜像的修改和自定义

    一.docker镜像的更新 (1)启动镜像,写入一些文件或者更新软件 docker run -it 3afd47092a0e[root@44652ba46352 /]# ls (2)更新镜像 dock ...

  5. php 安装 redis扩展

    https://segmentfault.com/a/1190000009422920 wget 源码编译

  6. JavaScript两数相加(踩坑)记录

    Adding two numbers concatenates them instead of calculating the sum JavaScript里两个变量 var a = 2: var b ...

  7. 用DELPHI 开发压缩、解压、自解压、加密

    引 言:在日常中,我们一定使用过WINZIP.WINRAR这样的出名的压缩软件,就是我们开发软件过程中不免要遇到数据加密.数据压缩的问题!本文中就这一技术问题展开探讨,同时感谢各位网友的技巧,在我每次 ...

  8. CentOS7统计某个进程当前的线程数

    方式一: cat /proc/[pid]/status 展示结果中,Threads后边对应的数字就是进程拥有的线程数量 方式二: |wc -l

  9. 如何导入数据到Mysql

    有两种方法: 1.如果是.sql后缀的数据库文件,使用phpmyadmin中的导入功能导入即可,导入前需要新建数据库名. 2.如果导入的是文件夹(内含.frm,.myd,.myi,.opt类型文件), ...

  10. 表格中上移下移置顶的js操作

    <script> $(function(){  //上移  var $up = $(".up")  $up.click(function() {   var $tr = ...