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 n1, n2 and n (1 ≤ n1, n2 ≤ 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
#include
#include
#include
using namespace std;
priority_queue , less > qmax;
priority_queue , greater > qmin;
int main()
{
int num,i,minus;
long long sum;
int n,m,k;
int minsize,maxsize;
while (scanf("%d%d%d",&m,&n,&k),m || n || k)
{
minsize = maxsize = 0;
sum = 0;
for (i = 0; i < k; i ++)
{
scanf("%d",&num);
sum += (long long)num;
if (minsize < m)
{
qmin.push(num);
minsize ++;
}
else
{
if (num > qmin.top())
{
qmin.pop();
qmin.push(num);
}
}
if (maxsize < n)
{
qmax.push(num);
maxsize ++;
}
else
{
if (num < qmax.top())
{
qmax.pop();
qmax.push(num);
}
}
}
minus = 0;
while (!qmax.empty())
{
minus += qmax.top();
qmax.pop();
}
while (!qmin.empty())
{
minus += qmin.top();
qmin.pop();
}
printf("%f\n",(1.0 * sum - (long long)minus) / (1.0 * (k - m - n)));
}
return 0;
}
import java.io.BufferedInputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.text.DecimalFormat;
import java.text.NumberFormat;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
public class Average {
// 输入文本路径
private static final String FILE_IN = "F:/workspace/files/average-in";
// 输出文本路径
private static final String FILE_OUT = "F:/workspace/files/average-out";
public static void main(String[] args) throws IOException {
File in = new File(FILE_IN); // 程序输入值，具体见题，该为文件路径
File out = new File(FILE_OUT);// 程序输出值，具体见题，该为文件路径
FileInputStream fileReader = new FileInputStream(in);
FileOutputStream outFile = new FileOutputStream(out);
Scanner sc = new Scanner(new BufferedInputStream(fileReader));
NumberFormat formatter = new DecimalFormat("#.000000");
int lines = 0;
String str = sc.nextLine();
int biggestSize = 0, smallestSize = 0;
while (!str.equals("0 0 0")) {
lines++;
List<Integer> lists = turnStringToIntList(str);
if (lines % 2 == 0) {
outFile.write((formatter.format(getAverage(lists, biggestSize, smallestSize)) + "\n").getBytes());
lists = new ArrayList<Integer>();
} else {
biggestSize = lists.get(0);
smallestSize = lists.get(1);
}
str = sc.nextLine();
}
outFile.close();
sc.close();
}
/**
* 将数字字符串转换为数字列表
*
* @param str
* @return
*/
private static List<Integer> turnStringToIntList(String str) {
String[] strs = str.split(" ");
List<Integer> lists = new ArrayList<Integer>();
for (String s : strs) {
lists.add(Integer.parseInt(s));
}
return lists;
}
/**
* 获取平均值
*
* @param lists
* 数字列表
* @param biggestSize
* 去掉最大数的个数
* @param smallestSize
* 去掉最小数的个数
* @return
*/
private static double getAverage(List<Integer> lists, int biggestSize, int smallestSize) {
// 将打的分数由低到高排序
Collections.sort(lists);
double sum = 0.0;
int inc = 0;
// 去掉最小数的个数和最大数的个数后循环相加
for (int i = smallestSize; i < lists.size() - biggestSize; i++) {
sum += lists.get(i);
inc++;
}
return sum / inc;
}
}