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的妙用的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。