2015年百度之星初赛(1) --- D KPI

简介: KPI Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 170    Accepted Submission(s): 59 Problem Description 你工作以后, KPI 就是你的全部了. 我开发了一个服务,取得了很大的知名度。

KPI

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

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

 

Input
有大约100组数据。

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

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

为了让题目简单,所有的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

Problem's Link:   http://acm.hdu.edu.cn/showproblem.php?pid=5249


 

Mean: 

 

analyse:

vector直接水过。

Time complexity: O(n)

 

Source code: 

 

/*
* this code is made by crazyacking
* Verdict: Accepted
* Submission Date: 2015-05-30-22.26
* Time: 0MS
* Memory: 137KB
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <Stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define  LL long long
#define  ULL unsigned long long
using namespace std;
vector<int> V;
int n;
char ord[10];
int num;
int Stack[10010];
int l,r;
int siz;
inline void solve()
{
    V.clear();
    V.reserve(n+10);
    r=0;
    l=1;
    siz=0;
    for (int i=1;i<=n;i++)
        {
        scanf("%s",ord);
        if (ord[0]=='i') scanf("%d",&Stack[++r]);
        if (ord[0]=='i')
        {
            siz++;
            V.insert(upper_bound(V.begin(),V.end(),Stack[r]),Stack[r]);
        }else if (ord[0]=='o')
        {
            V.erase(lower_bound(V.begin(),V.end(),Stack[l]));
            l++;
            siz--;
        }else{
            printf("%d\n",V[siz/2]);
        }
    }
}

int T;
int main(){
    while(scanf("%d",&n)!=EOF)
        {
        T++;
        printf("Case #%d:\n",T);
        solve();
    }
    return 0;
}
View Code

 

目录
相关文章
|
6月前
|
存储 Kubernetes 容器
百度搜索:蓝易云【Kubernetes使用helm部署NFS Provisioner】
现在,你已经成功使用Helm部署了NFS Provisioner,并且可以在Kubernetes中创建使用NFS存储的PersistentVolumeClaim。
200 10
|
6月前
百度搜索:蓝易云【什么是HTTP长轮询?】
现在,HTTP长轮询逐渐被WebSocket等更高效的实时通信技术所替代,但了解HTTP长轮询仍然有助于理解实时数据推送的基本原理。
126 9
|
6月前
|
移动开发 Shell Linux
百度搜索:蓝易云【Shell错误:/bin/bash^M: bad interpreter: No such file or directory】
将 `your_script.sh`替换为你的脚本文件名。运行此命令后,脚本文件的换行符将被转换为Linux格式,然后就可以在Linux系统上正常执行脚本了。
73 8
|
6月前
百度搜索:蓝易云【ipmitool配置BMC的ip】
以上操作将配置BMC的IP地址为新的值。请注意,操作BMC需要谨慎,确保你对服务器有足够的权限,并且仔细检查新的IP地址、子网掩码和默认网关,以免导致服务器网络失联。
100 7
|
6月前
|
Kubernetes 应用服务中间件 nginx
百度搜索:蓝易云【使用Kubernetes部署Nginx应用教程】
现在,你已经成功在Kubernetes集群上部署了Nginx应用。通过访问Service的外部IP地址,你可以访问Nginx服务。
81 4
|
6月前
|
缓存 网络协议 Linux
百度搜索:蓝易云【解决github push/pull报错443】
通过以上方法,你有望解决GitHub push/pull报错443的问题。如果问题仍然存在,建议检查GitHub的状态页面,看是否有正在维护或故障的情况。
132 3
|
6月前
|
Linux Perl
百度搜索:蓝易云【Linux常用命令awk】
以上仅是awk命令的一些常见用法,它还有许多更复杂的功能和用法,可以根据需要灵活运用。awk在文本处理和数据分析中非常实用,是Linux系统中的一把利器。
55 2
|
6月前
|
编解码 应用服务中间件 nginx
百度搜索:蓝易云【基于Nginx与Nginx-rtmp-module实现】
综上所述,基于Nginx与Nginx-rtmp-module的组合,可以搭建一个功能强大的流媒体服务器,用于实现直播和点播服务。
80 1
|
6月前
|
Linux
百度搜索:蓝易云【Linux系统ps命令:查看正在运行的进程】
通过这些简洁的ps命令用法,你可以方便地查看Linux系统中正在运行的进程信息。
85 1