表演评分问题

一 问题描述

在演讲比赛中，评委对参赛者的表演进行评分。评分方法，给定 n 个正整数评分，删除最大的 n1 个和最小的 n2 个评分，将其余评分的平均值作为参赛者的最终成绩。请给出参赛者的最终成绩。

二 输入和输出

1 输入

输入包括 n 个测试用例，每个测试用例都包含两行：第 1 行包含三个整数 n1、n2 和 n。第2 行包括 n 个正整数 ai。在最后的一个测试用例后跟 3个0.

2 输出

对每个测试用例都单行输出参赛者的最终成绩，保留小数点后 6 位。

三 输入和输出样例

1 输入样例

1 2 5

1 2 3 4 5

4 2 10

2121187 902 485 531 843 582 652 926 220 155

0 0 0

2 输出样例

3.500000

562.500000

四 算法分析和设计

1 分析

只需用两个队列分别存储最大的 n1 个数和最小的 n2 个数即可。

2 设计

定义两个优先队列，q1 最大值优先，存储最小的 n2 个数；q2 最小值优先，存储最大的 n1 个数。用总和减去这两个优先队列的元素值，然后求平均值。

五 代码

package com.platform.modules.alg.alglib.poj2833;
 
import java.util.Comparator;
import java.util.PriorityQueue;
 
public class Poj2833 {
    public String output = "";
 
    class MyComparator implements Comparator {
        public int compare(Integer num1, Integer num2) {
            return num2.compareTo(num1);
        }
    }
 
    public String cal(String input) {
        int n1, n2, n, i, x;
        long sum;
        String[] line = input.split("\n");
 
        String[] words = line[0].split(" ");
        n1 = Integer.parseInt(words[0]);
        n2 = Integer.parseInt(words[1]);
        n = Integer.parseInt(words[2]);
 
        PriorityQueue q1 = new PriorityQueue<>(new MyComparator()); // 最大值优先,保存最小的 n2 个
        PriorityQueue q2 = new PriorityQueue<>(); // 默认为小顶堆,保存最大的 n1 个
        sum = 0;
        String[] numbers = line[1].split(" ");
        for (i = 0; i < n; i++) {
            x = Integer.parseInt(numbers[i]);
            sum += x;
            q1.add(x);
            q2.add(x);
            if (q1.size() > n2)
                q1.poll();
            if (q2.size() > n1)
                q2.poll();
        }
        while (!q1.isEmpty()) {
            sum -= q1.poll();
        }
        while (!q2.isEmpty()) {
            sum -= q2.poll();
        }
        output = String.format("%.6f", 1.0 * sum / (n - n1 - n2));
        return output;
    }
}

六 测试