[Swust OJ 1094]--中位数（巧用set，堆排序）

题目链接：http://acm.swust.edu.cn/problem/1094/

Time limit(ms): 1000　　　　　　Memory limit(kb): 32768

中位数（又称中值，英语：Median），统计学中的专有名词，代表一个样本、种群或概率分布中的一个数值，其可将数值集合划分为相等的上下两部分。对于有限的数集，可以通过把所有观察值高低排序后找出正中间的一个作为中位数。如果观察值有偶数个，则中位数不唯一，通常取最中间的两个数值的平均数作为中位数。

Description

多组输入

第一行：一个正整数N (0<N<1000000)
第二行：N个正整数。(0=<A[i]<2^30)

Input

每组数据先输出”Case X:”,X表示测试数据的编号，从1开始。

第二行输出N个数，第i个数对应数组前i个值的中位数。（精确到小数点后一位）

Output

5
1 2 3 4 5
6
2 5 4 8 7 4
 

Sample Input

Case 1:
1.0 1.5 2.0 2.5 3.0
Case 2:
2.0 3.5 4.0 4.5 5.0 4.5
 

Sample Output

输出换行请使用

Hint

swust第10届校赛

解题思路：由于数据量太大，那么解题关键就在排序上面了，那么可以巧用堆排序，或者是使用容器 multiset(允许存在相同元素)，那么就不会超时了。

multiset 容器用法：http://www.cnblogs.com/zyxStar/p/4542835.html

下面是巧用容器的代码

 1 #include <iostream>
 2 #include <set>
 3 #include <cstdio>
 4 using namespace std;
 5  
 6 #define rep(i,a,b) for(int i=a;i<=b;i++)
 7 int t, n;
 8 multiset<double>mpt;
 9  
10 void mid_num(){
11     double x;
12     printf("Case %d:
", ++t);
13     mpt.clear();
14     scanf("%lf", &x);
15     mpt.insert(x);
16     multiset <double> ::iterator it = mpt.begin();
17     printf("%.1lf", x);
18     rep(i, 2, n){
19         scanf("%lf", &x);
20         mpt.insert(x);
21         if (x < *it){
22             if (i & 1) printf(" %.1lf", *(--it));
23             else {
24                 multiset <double> ::iterator it1 = it;
25                 printf(" %.1lf", (*it + *(--it1)) / 2.0);
26             }
27         }
28         else {
29             if (i & 1) printf(" %.1lf", *it);
30             else {
31                 ++it;
32                 multiset <double> ::iterator it1 = it;
33                 printf(" %.1lf", (*it + *(--it1)) / 2.0);
34  
35             }
36         }
37     }
38     printf("
");
39 }
40  
41 int main(){
42     while (~scanf("%d", &n))
43         mid_num();
44     return 0;
45 }

View Code

堆排序的代码也贴出来吧（原谅我太懒没有优化这代码~~~）

 1 #include <stdio.h>
 2 #include <string.h>
 3 int lstack[500001], ltot, rstack[500001], rtot, mid;
 4 int Max(int a, int b){
 5     return a > b ? a : b;
 6 }
 7 int Min(int a, int b){
 8     return a<b ? a : b;
 9 }
10 void lup(int step){
11     while (step != 1){
12         if (lstack[step]>lstack[step / 2])lstack[step] ^= lstack[step / 2] ^= lstack[step] ^= lstack[step / 2];
13         else break;
14         step = step / 2;
15     }
16     if (step == 1 && lstack[1] > mid) lstack[1] ^= mid ^= lstack[1] ^= mid;
17 }
18 void ldown(){
19     if (ltot > 1 && mid < lstack[1]) mid ^= lstack[1] ^= mid ^= lstack[1];
20     else return;
21     int step = 1;
22     while (step * 2 < ltot){
23         if (step * 2 + 1 >= ltot){
24             if (lstack[step] < lstack[step * 2])
25                 lstack[step] ^= lstack[step * 2] ^= lstack[step] ^= lstack[step * 2], step = step * 2;
26             else return;
27         }
28         else{
29             if (lstack[step] <= lstack[step * 2] && lstack[step * 2 + 1] <= lstack[step * 2])
30                 lstack[step] ^= lstack[step * 2] ^= lstack[step] ^= lstack[step * 2], step = step * 2;
31             else if (lstack[step] <= lstack[step * 2 + 1] && lstack[step * 2] <= lstack[step * 2 + 1])
32                 lstack[step] ^= lstack[step * 2 + 1] ^= lstack[step] ^= lstack[step * 2 + 1], step = step * 2 + 1;
33             else return;
34         }
35     }
36 }
37 void rup(int step){
38     while (step != 1){
39         if (rstack[step]<rstack[step / 2])rstack[step] ^= rstack[step / 2] ^= rstack[step] ^= rstack[step / 2];
40         else break;
41         step = step / 2;
42     }
43     if (step == 1 && rstack[1]<mid) rstack[1] ^= mid ^= rstack[1] ^= mid;
44 }
45 void rdown(){
46     if (rtot>1 && mid>rstack[1]) mid ^= rstack[1] ^= mid ^= rstack[1];
47     else return;
48     int step = 1;
49     while (step * 2 < rtot){
50         if (step * 2 + 1 >= rtot){
51             if (rstack[step] > rstack[step * 2])
52                 rstack[step] ^= rstack[step * 2] ^= rstack[step] ^= rstack[step * 2], step = step * 2;
53             else return;
54         }
55         else{
56             if (rstack[step] >= rstack[step * 2] && rstack[step * 2 + 1] >= rstack[step * 2])
57                 rstack[step] ^= rstack[step * 2] ^= rstack[step] ^= rstack[step * 2], step = step * 2;
58             else if (rstack[step] >= rstack[step * 2 + 1] && rstack[step * 2] >= rstack[step * 2 + 1])
59                 rstack[step] ^= rstack[step * 2 + 1] ^= rstack[step] ^= rstack[step * 2 + 1], step = step * 2 + 1;
60             else return;
61         }
62     }
63 }
64 int main()
65 {
66     int t = 1, n, i;
67     while (scanf("%d", &n) != EOF){
68         printf("Case %d:
", t++);
69         scanf("%d", &mid);
70         ltot = rtot = 1;
71         printf("%.1lf", (double)mid);
72         for (i = 1; i < n; i++){
73             if (i % 2){
74                 scanf("%d", &lstack[ltot]);
75                 lup(ltot);
76                 rdown();
77                 ltot++;
78                 printf(" %.1lf", (mid + lstack[1]) / 2.0);
79             }
80             else{
81                 scanf("%d", &rstack[rtot]);
82                 rup(rtot);
83                 ldown();
84                 rtot++;
85                 printf(" %.1lf", (double)mid);
86             }
87         }
88         printf("
");
89     }
90     return 0;
91 }

View Code