**题意(中问题直接粘题意吧)
KPI
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
思路:
**
题意要求动态的求中位数,我的方法是开两个优先队列,然后左边升序,右边降序,右边个数-左边个数>=1,然后右边询问的时候直接输出右边最小的,删除的时候就直接mark上(不是马上从队列里面拿出来),然后看看是左边还是右边的,把对应的那边的个数-1,如果发现(右边个数-左边个数>=1)这个条件不满足了,那么就权衡下,两个队列里面的元素处理下(左给右或者右给左),总的时间复杂度与数据无关,是O(n*log(n))的。
#include<stack>
#include<map>
#include<queue>
#include<stdio.h>
#include<string.h>
using namespace std;
typedef struct L
{
int x;
friend bool operator < (L a ,L b)
{
return a.x < b.x;
}
}L;
typedef struct R
{
int x;
friend bool operator < (R a ,R b)
{
return a.x > b.x;
}
}R;
R xinr ,tour;
L xinl ,toul;
priority_queue<L>lq;
priority_queue<R>rq;
queue<int>qq;
map<int ,int>mark;
int main ()
{
int n ,cas = 1 ,i ,a;
char str[10];
while(~scanf("%d" ,&n))
{
while(!lq.empty())lq.pop();
while(!rq.empty())rq.pop();
while(!qq.empty())qq.pop();
mark.clear();
int ls = 0 ,rs = 0;
printf("Case #%d:\n" ,cas ++);
while(n--)
{
scanf("%s" ,str);
if(str[0] == 'i')
{
scanf("%d" ,&a);
mark[a] = 1;
qq.push(a);
if(ls == rs)//往右放
{
rs ++;
if(ls == 0)
{
xinr.x = a;
rq.push(xinr);
}
else
{
toul = lq.top();
xinr.x = a;
if(toul.x < a) rq.push(xinr);
else
{
lq.pop();
tour.x=toul.x;
rq.push(tour);
xinl.x=xinr.x;
lq.push(xinl);
}
}
}
else //往左放
{
ls ++;
tour = rq.top();
xinl.x = a;
if(tour.x > a) lq.push(xinl);
else
{
rq.pop();
toul.x=tour.x;
lq.push(toul);
xinr.x=xinl.x;
rq.push(xinr);
}
}
}
if(str[0] == 'o')
{
int tou = qq.front();
qq.pop();
if(tou >= rq.top().x) rs --;
else ls --;
mark[tou] = 0;
if(ls > rs) //->
{
ls -- ,rs ++;
xinr.x = lq.top().x;
lq.pop();
rq.push(xinr);
}
if(rs - ls == 2)
{
ls ++ ,rs --;
xinl.x = rq.top().x;
rq.pop();
lq.push(xinl);
}
}
if(str[0] == 'q')
{
printf("%d\n" ,rq.top().x);
}
while(!lq.empty())
{
if(!mark[lq.top().x])
lq.pop();
else break;
}
while(!rq.empty())
{
if(!mark[rq.top().x])
rq.pop();
else break;
}
}
}
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章