文档章节

poj 2833 The Average

locusxt
 locusxt
发布于 2013/12/22 18:11
字数 443
阅读 34
收藏 0
poj

The Average
Time Limit: 6000MS Memory Limit: 10000K
Total Submissions: 8989 Accepted: 2811
Case Time Limit: 4000MS

Description

In a speech contest, when a contestant finishes his speech, the judges will then grade his performance. The staff remove the highest grade and the lowest grade and compute the average of the rest as the contestant’s final grade. This is an easy problem because usually there are only several judges.

Let’s consider a generalized form of the problem above. Given n positive integers, remove the greatest n1 ones and the least n2 ones, and compute the average of the rest.

Input

The input consists of several test cases. Each test case consists two lines. The first line contains three integers n1n2 and n (1 ≤ n1n2 ≤ 10, n1 + n2 < n ≤ 5,000,000) separate by a single space. The second line contains n positive integers ai (1 ≤ ai ≤ 108 for all i s.t. 1 ≤ i ≤ n) separated by a single space. The last test case is followed by three zeroes.

Output

For each test case, output the average rounded to six digits after decimal point in a separate line.

Sample Input

1 2 5
1 2 3 4 5
4 2 10
2121187 902 485 531 843 582 652 926 220 155
0 0 0

Sample Output

3.500000
562.500000

Hint

This problem has very large input data. scanf and printf are recommended for C++ I/O.

The memory limit might not allow you to store everything in the memory.

Source

[Submit]   [Go Back]   [Status]   [Discuss]

/*=============================================================================
#     FileName: 2833.cpp
#         Desc: 
#       Author: zhuting
#        Email: cnjs.zhuting@gmail.com
#     HomePage: my.oschina.net/locusxt
#      Version: 0.0.1
#    CreatTime: 2013-12-22 18:12:25
#   LastChange: 2013-12-22 18:12:25
#      History:
=============================================================================*/
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;

int main()
{
	int n1 = 0, n2 = 0, n = 0;
	int tmp = 0;
	while (true)
	{
		long long ans = 0;
		int pqn1 = 0, pqn2 = 0;
		priority_queue<int, vector<int>, greater<int> > pq1;
		priority_queue<int, vector<int>, less<int> > pq2;
		scanf("%d%d%d", &n1, &n2, &n);
		if (n1 == 0 && n2 == 0 && n == 0)
			break;
		for (int i = 0 ; i < n; ++i)
		{
			scanf("%d", &tmp);
			ans += tmp;
			if (pqn1 < n1)
			{
				pq1.push(tmp);
				++pqn1;
			}
			else
			{
				if (tmp > pq1.top())
				{
					pq1.pop();
					pq1.push(tmp);
				}
			}
			if (pqn2 < n2)
			{
				pq2.push(tmp);
				++pqn2;
			}
			else
			{
				if (tmp < pq2.top())
				{
					pq2.pop();
					pq2.push(tmp);
				}
			}
		}
		for (int i = 0 ; i < n1; ++i)
		{
			ans -= pq1.top();
			pq1.pop();
		}
		for (int i = 0 ; i < n2; ++i)
		{
			ans -= pq2.top();
			pq2.pop();
		}

		printf("%.6lf\n", ((double)ans) / (double)(n - n1 - n2));
	}
	return 0;
}




© 著作权归作者所有

上一篇: poj 2255 Tree Recovery
下一篇: poj 2442 Sequence
locusxt
粉丝 27
博文 140
码字总数 90989
作品 0
海淀
程序员
私信 提问
POJ 1004 Financial Management

Financial Management Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 164661 Accepted: 61136 Description Larry graduated this year and finally has a job. He's making a......

圣洁之子
2015/06/17
122
0
算法进阶路径

第一阶段:练经典常用算法,下面的每个算法给我打上十到二十遍,同时自己精简代码, 因为太常用,所以要练到写时不用想,10-15分钟内打完,甚至关掉显示器都可以把程序打 出来. 1.最短路(Fl...

暖冰
2016/04/02
163
1
一个搞ACM需要掌握的算法

ACM的竞赛性强,因此自己应该和自己的实际应用联系起来.适合自己的才是好的,有的人不适合搞算法,喜欢系统架构,因此不要看到别人什么就眼红,发挥自己的长处,这才是重要的. 第一阶段:练经典常用...

long0404
2015/06/24
0
0
asterisk如何把sip info转换到2833

我有两台设备注册到asterisk,一台设备只能使用sip info,另一台只支持2833,他们之间需要通过DTMF来控制通话,不知道asterisk能否自动将这两种协议转换?

tensecond
2014/02/13
273
0
Java SIP软电话--jPhoneLite

jphonelite 是一个使用 Java SIP 技术开发的 VoIP 软电话。Features 6 lines with transfer, hold, conference (up to all 6 lines), contact list, recent calls, g711, g729a and RFC 283......

匿名
2010/09/24
7.1K
1

没有更多内容

加载失败,请刷新页面

加载更多

XXL-JOB使用命令行的方式启动python时,日志过多导致阻塞的解决方式

一、Runtime.getRuntime().exec()的阻塞问题 这个问题也不能算是XXL-JOB的问题,而是Java的Runtime.getRuntime().exec()造成的,BufferedReader的缓冲区大小有限,当不能及时从缓冲区中把输出...

codeobj
2分钟前
0
0
java后端获取字符串标签里面的具体值

1、如下:怎么获取value值,使用Jsoup解决 <select id='department' name='department' class='select' tabindex='6' onchange='changeDept()'><option value=''>院系</optio......

木九天
9分钟前
2
0
Xamarin图表开发基础教程(10)OxyPlot框架支持的图表类型

Xamarin图表开发基础教程(10)OxyPlot框架支持的图表类型 OxyPlot组件支持26种图表,这些图表按照功能和样式可以分为4大类,分别为线型图表、条型图表、金融图表和其它图表。 线型图表 OxyP...

大学霸
13分钟前
2
0
移动端input“输入框”常见问题及解决方法

移动端input“输入框”常见问题及解决方法 1. ios中,输入框获得焦点时,页面输入框被遮盖,定位的元素位置错乱: 当页input存在于吸顶或者吸底元素中时,用户点击输入框,输入法弹出后,fie...

tyou
14分钟前
2
0
初探Android线程池

前言 最近在看OkHttp的源码,看的时候发现有关线程池的运用,自己就仔细想了一下,这个块知识好像不是很牢固。没办法,再研究一下有关线程池的相关知识吧。学习就是一个查漏补缺的过程,最终...

二营长的意大利炮手
21分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部