KPI

Time Limit: 20 Sec Memory Limit: 256 MB

题目连接

http://acdream.info/problem?pid=1754

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

HINT

题意

题解：

用一个set大法！

代码：

//qscqesze

#include <cstdio>

#include <cmath>

#include <cstring>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <set>

#include <vector>

#include <sstream>

#include <queue>

#include <typeinfo>

#include <fstream>

#include <map>

#include <stack>

typedef long long ll;

using namespace std;

//freopen("D.in","r",stdin);

//freopen("D.out","w",stdout);

#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)

#define test freopen("test.txt","r",stdin)

#define maxn 2000001

#define mod 10007

#define eps 1e-9

int Num;

char CH[];

const int inf=0x3f3f3f3f;

const ll infll = 0x3f3f3f3f3f3f3f3fLL;

inline ll read()

{

    ll x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

inline void P(int x)

{

    Num=;if(!x){putchar('');puts("");return;}

    while(x>)CH[++Num]=x%,x/=;

    while(Num)putchar(CH[Num--]+);

    puts("");

}

//**************************************************************************************

queue<ll> q;

set<ll> ss;

ll t,n,mid;

char cmd[];

void insert(ll x)

{

    ss.insert(x);

    if(mid==-)

    {

        mid=x;

    }

    else

    {

        if(x>mid)

            if(ss.size()%==)

                mid=*ss.upper_bound(mid);

            else

            {

                if(ss.size()%==)

                    mid=*(--ss.lower_bound(mid));

            }

    }

    q.push(x);

}

void dequeue()

{

    ll num=q.front();

    q.pop();

    ss.erase(num);

    if(ss.empty())

    {

        mid=-;

    }

    else

    {

        if(num>mid)

        {

            if(ss.size()%==)

                mid=*(--ss.lower_bound(mid));

            else if(num<mid)

            {

                if(ss.size()%==)

                    mid=*ss.upper_bound(mid);

            }

            else

            {

                if(ss.size()%==)

                    mid=*ss.upper_bound(mid);

                else

                    mid=*(--ss.lower_bound(mid));

            }

        }

    }

}

void solve()

{

    n=read();

    mid=-;

    ss.clear();

    while(!q.empty())

        q.pop();

    for(int i=;i<=n;i++)

    {

        scanf("%s",cmd);

        if(cmd[]=='i')

        {

            int x=read();

            insert(x);

        }

        if(cmd[]=='o')

            dequeue();

        if(cmd[]=='q')

            printf("%lld\n",mid);

    }

}

int main()

{

    //test;

    //freopen("1.out","w",stdout);

    int t=;

    for(int cas=;cas<=t;cas++)

    {

        printf("Case #%d:\n",cas);

        solve();

    }

}

KPI

2015 百度之星 1004 KPI STL的妙用

KPI

题目连接

Description

Sample Output