PKU 2833-The Average

問題概要

n個の要素の数列がある．大きい順にn1個と小さい順にn2個の要素を無視したときの平均値を求めよ．

解法

優先順序付きキューを用いて無視するものを記憶する．

実装(C++)

#include <iostream>
#include <algorithm>
#include <queue>
#include <functional>
#include <cstdio>
using namespace std;

int readint(){
	int t;
	scanf("%d",&t);
	return t;
}
int data[25];
int main() {
	int n1,n2,n;
	for(;;){
		n1=readint();n2=readint();n=readint();
		if(n1==0)break;
		swap(n1,n2);
		for(int i=0;i<n1+n2;i++){
			data[i]=readint();
		}
		sort(data,data+n1+n2);
		priority_queue<int> low;priority_queue<int,vector<int>,greater<int> > high;
		for(int i=0;i<n1+n2;i++){
			if(i<n1)low.push(data[i]);
			else high.push(data[i]);
		}
		long long ans=0;
		int q;
		for(int i=0;i<n-n1-n2;i++){
			q=readint();
			if(q<low.top()){
				ans+=low.top();low.pop();
				low.push(q);
			}else if(q>high.top()){
				ans+=high.top();high.pop();
				high.push(q);
			}else{
				ans+=q;
			}
		}
		printf("%.6f\n",ans/(double)(n-n1-n2));
	}
	return 0;
}