pku 2833給出n個(gè)數(shù)字，n <= 5000000，要求去掉最大的
n1個(gè)數(shù)和最小的
n2 個(gè)數(shù)，求剩下的數(shù)的平均值。
題目要求不能存儲(chǔ)完所有的n個(gè)數(shù)再統(tǒng)計(jì)，所以要隨著輸入來動(dòng)態(tài)統(tǒng)計(jì)。
思路：
設(shè)已輸入最大的
n1個(gè)數(shù)和最小的
n2 個(gè)數(shù)。剩下的數(shù)有n-
n2-
n1個(gè)。每輸入一個(gè)數(shù) x ，都維護(hù)這個(gè)invariance，則算法結(jié)束時(shí)就得到題目要求的結(jié)果：
avg=((avg*cnt)+a)/(cnt+1), cnt=cnt+1
其中a這樣定義：若x小于
n2個(gè)數(shù)中的最大值a
max，則x與a
max交換，且a為a
max；否則若x大于
n1個(gè)數(shù)中的最小值a
min，則x與a
min交換，且a為a
min；否則a就為x。
這樣我們就動(dòng)態(tài)地維護(hù)了兩個(gè)數(shù)組：一個(gè)是當(dāng)前已輸入的數(shù)中的最大的
n2個(gè)，另一個(gè)為當(dāng)前已輸入的數(shù)中最小的
n1個(gè)，且avg是當(dāng)前的答案。這個(gè)invariance一直維護(hù)到算法結(jié)束就得到結(jié)果。
雖然這里的思想很簡單，但是維護(hù)invariance這種證明思路是Introduction to Algorithms中常用的。
回到題目，我用兩個(gè)堆（一個(gè)大頂堆一個(gè)小頂堆）分別維護(hù)兩個(gè)數(shù)組，每次輸入一個(gè)新的數(shù)（假設(shè)前面的
n1 +
n2 個(gè)已輸入），就按上面的思路來維護(hù)。這里的
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];// 存儲(chǔ)最大的m個(gè)數(shù)，與存儲(chǔ)最小的l個(gè)數(shù)
11 int ca,cb; //a，b存儲(chǔ)了多少數(shù)字
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 }