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"操作。
每组数据第一行有一个$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"，输出当前管道内重要值的中间值。
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; }
