pku 2833给出n个数字，n <= 5000000，要求去掉最大的
n1个数和最小的
n2 个数，求剩下的数的平均值。
题目要求不能存储完所有的n个数再统计，所以要随着输入来动态统计。
思路：
设已输入最大的
n1个数和最小的
n2 个数。剩下的数有n-
n2-
n1个。每输入一个数 x ，都维护这个invariance，则算法结束时就得到题目要求的结果：
avg=((avg*cnt)+a)/(cnt+1), cnt=cnt+1
其中a这样定义：若x小于
n2个数中的最大值a
max，则x与a
max交换，且a为a
max；否则若x大于
n1个数中的最小值a
min，则x与a
min交换，且a为a
min；否则a就为x。
这样我们就动态地维护了两个数组：一个是当前已输入的数中的最大的
n2个，另一个为当前已输入的数中最小的
n1个，且avg是当前的答案。这个invariance一直维护到算法结束就得到结果。
虽然这里的思想很简单，但是维护invariance这种证明思路是Introduction to Algorithms中常用的。
回到题目，我用两个堆（一个大顶堆一个小顶堆）分别维护两个数组，每次输入一个新的数（假设前面的
n1 +
n2 个已输入），就按上面的思路来维护。这里的
n1 n2 都比较小，所以堆的效果可能不是很明显。
1
2 #include <iostream>
3 #include <algorithm>
4 //#include <set>
5
6 using namespace std;
7
8 long i,j,k;
9 int m,l,n;
10 double a[110],b[110];// 存储最大的m个数，与存储最小的l个数
11 int ca,cb; //a，b存储了多少数字
12
13 // 插入x并返回堆顶元素
14 void insert_mx_heap(int x)
15 {
16 a[++ca]=x;
17 int cur=ca;
18 while(cur>1 && a[cur]<a[cur>>1]){
19 int tmp=a[cur>>1];
20 a[cur>>1]=a[cur];
21 a[cur]=tmp;
22 cur=cur>>1;
23 }
24 }
25
26 void insert_mn_heap(int x)
27 {
28 b[++cb]=x;
29 int cur=cb;
30 while(cb>1 && b[cur]>b[cur>>1]){
31 int tmp=b[cur>>1];
32 b[cur>>1]=b[cur];
33 b[cur]=tmp;
34 }
35 }
36
37 void siftdown_mx(int x)
38 {
39 a[1]=x;
40 int cur=1;
41 while((cur<<1)<=ca){
42 int j=cur<<1;
43 if((j+1)<=ca && a[j+1]<a[j]) j++;
44 if(a[j]>a[cur]) break;
45 int tmp=a[cur];
46 a[cur]=a[j];
47 a[j]=tmp;
48 cur=j;
49 }
50 }
51
52 void siftdown_mn(int x)
53 {
54 b[1]=x;
55 int cur=1;
56 while((cur<<1)<=cb){
57 int j=cur<<1;
58 if((j+1)<=cb && b[j+1]>b[j]) j++;
59 if(b[j]<b[cur]) break;
60 int tmp=b[cur];
61 b[cur]=b[j];
62 b[j]=tmp;
63 cur=j;
64 }
65 }
66
67 int main()
68 {
69 //freopen("in.txt","r",stdin);
70 while(scanf("%d%d%ld",&m,&l,&n) && n!=0)
71 {
72 ca=cb=0;
73 int in;
74 double avg=0;
75 int cnt;
76 int tmp[21];
77 for(i=0;i<m+l;i++) scanf("%d",&tmp[i]);
78 sort(tmp,tmp+m+l);
79 for(i=0;i<l;i++) insert_mn_heap(tmp[i]);
80 for(i=l;i<m+l;i++) insert_mx_heap(tmp[i]);
81 // 开始输入
82 cnt=0;
83 for(i=m+l;i<n;i++){
84 scanf("%d",&in);
85 // in大于最大组中最小值
86 if(in>a[1]){
87 avg=(avg*cnt+a[1])/(++cnt);
88 siftdown_mx(in);
89 }else if(in<b[1]){
90 avg=(avg*cnt+b[1])/(++cnt);
91 siftdown_mn(in);
92 }else{
93 avg=(avg*cnt+in)/(++cnt);
94 }
95 }
96 printf("%.6lf\n",avg);
97 }
98 return 1;
99 }