无序数组的中位数（set+deque）hdu5249

KPI

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

Problem Description

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

Input

有大约100组数据。

每组数据第一行有一个

Output

对于每组数据，先输出一行

Case #i:
然后每一次"query"，输出当前管道内重要值的中间值。

Sample Input

in 874

query

out

in 24622

in 12194

query

Sample Output

Case #1:

874

24622

分析：题目中说有值的加入和值的取出，首先可以用双端队列维护一个队列请求，即先进先出，用q.front()和q.pop_front()读取和删除队列头元素，用q.back()和q.push_back()读取和加入队尾元素，而维护队列的有序可以用set容器，分别建立两个容器sa和sb，无论是删除和加入元素的时候保证size(sa)==size(sb)或者size(sb)+1==size(sb);则sb.begin() 就是中位数的值

程序：

 1 #include"stdio.h"
 2 #include"string.h"
 3 #include"stdlib.h"
 4 #include"algorithm"
 5 #include"queue"
 6 #include"math.h"
 7 #include"iostream"
 8 #include"vector"
 9 #define M 100009
10 #define inf 0x3f3f3f3f
11 #define eps 1e-9
12 #define PI acos(-1.0)
13 #include"map"
14 #include"vector"
15 #include"set"
16 #include"string"
17 using namespace std;
18 int main()
19 {
20     int n,kk=1;
21     while(scanf("%d",&n)!=-1)
22     {
23         set<int>sa,sb;
24         sa.insert(-1);
25         sb.insert(1000000001);
26         deque<int>q;
27         printf("Case #%d:
",kk++);
28         while(n--)
29         {
30             char str[111];
31             scanf("%s",str);
32             if(strcmp(str,"in")==0)
33             {
34                 int k;
35                 scanf("%d",&k);
36                 q.push_back(k);
37                 sa.insert(k);
38                 int la=sa.size();
39                 int lb=sb.size();
40                 int u=*(sa.rbegin());
41                 int v=*(sb.begin());
42                 if(la>lb)
43                 {
44                     sa.erase(u);
45                     sb.insert(u);
46                 }
47                 u=*(sa.rbegin());
48                 v=*(sb.begin());
49                 if(u>v)
50                 {
51                     sb.erase(v);
52                     sa.insert(v);
53                     sa.erase(u);
54                     sb.insert(u);
55                 }
56             }
57             else if(strcmp(str,"out")==0)
58             {
59 
60                 int u=q.front();
61                 q.pop_front();
62                 sa.erase(u);
63                 sb.erase(u);
64 
65                 int la=sa.size();
66                 int lb=sb.size();
67                 if(la+2==lb)
68                 {
69                     sa.insert(*(sb.begin()));
70                     sb.erase(*(sb.begin()));
71                 }
72                 else if(la==lb+1)
73                 {
74                     sb.insert(*(sa.rbegin()));
75                     sa.erase(*(sa.rbegin()));
76                 }
77             }
78             else
79             {
80                 printf("%d
",*(sb.begin()));
81             }
82         }
83     }
84     return 0;
85 }
86 /*
87 
88 40
89 in 11
90 in 22
91 in 33
92 in 44
93 in 55
94 in 66
95 query
96 
97 */

View Code