2833.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Source

Problem Id:2833  User Id:fzk 
Memory:60K  Time:3828MS
Language:G++  Result:Accepted

Source 

#include <stdio.h>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;


int main( ) {
	int a, b, n, i, j, s;
	int g[10], gn, l[10], ln;

	while( 1 ) {
		scanf( "%d%d%d", &a, &b, &n );
		if( a == 0 && b == 0 && n == 0 )
			break;

		double sum = 0;
		gn = ln = 0;
		for( j=0; j<n; j++ ) {
			scanf( "%d", &s );
			sum += s;

			if( gn < a ) {
				g[gn++] = s;
				if( gn == a )
					sort( g, g+gn );
			}
			else {
				if( g[0] < s ) {
					for( i=1; i<gn && g[i] < s; i++ )
						g[i-1] = g[i];
					g[i-1] = s;
				}
			}

			if( ln < b ) {
				l[ln++] = s;
				if( ln == b )
					sort( l, l+ln, greater<int>() );
			}
			else {
				if( l[0] > s ) {
					for( i=1; i<ln && l[i] > s; i++ )
						l[i-1] = l[i];
					l[i-1] = s;
				}
			}

			
		}

		for( i=0; i<gn; i++ )
			sum -= g[i];
		for( i=0; i<ln; i++ )
			sum -= l[i];

		printf( "%.6lf\n", sum/(n-a-b) );
	}
	return 0;
}