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[20]; const int inf=0x3f3f3f3f; const ll infll = 0x3f3f3f3f3f3f3f3fLL; inline ll read() {ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f; } inline void P(int x) {Num=0;if(!x){putchar('0');puts("");return;}while(x>0)CH[++Num]=x%10,x/=10;while(Num)putchar(CH[Num--]+48);puts(""); } //************************************************************************************** queue<ll> q; set<ll> ss; ll t,n,mid; char cmd[100];void insert(ll x) {ss.insert(x);if(mid==-1){mid=x;}else{if(x>mid)if(ss.size()%2==0)mid=*ss.upper_bound(mid);else{if(ss.size()%2==1)mid=*(--ss.lower_bound(mid));}}q.push(x); } void dequeue() {ll num=q.front();q.pop();ss.erase(num);if(ss.empty()){mid=-1;}else{if(num>mid){if(ss.size()%2==1)mid=*(--ss.lower_bound(mid));else if(num<mid){if(ss.size()%2==0)mid=*ss.upper_bound(mid);}else{if(ss.size()%2==0)mid=*ss.upper_bound(mid);else mid=*(--ss.lower_bound(mid));}}} } void solve() {n=read();mid=-1;ss.clear();while(!q.empty())q.pop();for(int i=1;i<=n;i++){scanf("%s",cmd);if(cmd[0]=='i'){int x=read();insert(x);}if(cmd[0]=='o')dequeue();if(cmd[0]=='q')printf("%lld\n",mid);} } int main() {//test;//freopen("1.out","w",stdout);int t=1;for(int cas=1;cas<=t;cas++){printf("Case #%d:\n",cas);solve();} }

 

转载于:https://www.cnblogs.com/qscqesze/p/4542561.html

总结

以上是生活随笔为你收集整理的2015 百度之星 1004 KPI STL的妙用的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。