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 就是你的全部了. 我開發(fā)了一個(gè)服務(wù)，取得了很大的知名度。數(shù)十億的請(qǐng)求被推到一個(gè)大管道后同時(shí)服務(wù)從管頭拉取請(qǐng)求。讓我們來(lái)定義每個(gè)請(qǐng)求都有一個(gè)重要值。我的KPI是由當(dāng)前管道內(nèi)請(qǐng)求的重要值的中間值來(lái)計(jì)算。現(xiàn)在給你服務(wù)記錄，有時(shí)我想知道當(dāng)前管道內(nèi)請(qǐng)求的重要值得中間值。

?

Input 有大約100組數(shù)據(jù)。

每組數(shù)據(jù)第一行有一個(gè)$n (1 \leq n \leq 10000)$，代表服務(wù)記錄數(shù)。

接下來(lái)有n行，每一行有3種形式
??"in x": 代表重要值為$x (0 \leq x \leq 10^9)$的請(qǐng)求被推進(jìn)管道。
??"out": 代表服務(wù)拉取了管道頭部的請(qǐng)求。
??"query: 代表我想知道當(dāng)前管道內(nèi)請(qǐng)求重要值的中間值. 那就是說(shuō)，如果當(dāng)前管道內(nèi)有m條請(qǐng)求, 我想知道，升序排序后第$floor(m/2)+1_{th}$ 條請(qǐng)求的重要值.

為了讓題目簡(jiǎn)單，所有的x都不同，并且如果管道內(nèi)沒有值，就不會(huì)有"out"和"query"操作。

?

Output 對(duì)于每組數(shù)據(jù)，先輸出一行

Case #i:
然后每一次"query"，輸出當(dāng)前管道內(nèi)重要值的中間值。

?

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直接水過(guò)。

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

?

總結(jié)

以上是生活随笔為你收集整理的2015年百度之星初赛(1) --- D KPI的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。