L2-015 互评成绩

学生互评作业的简单规则是这样定的：每个人的作业会被 \(k\) 个同学评审，得到 \(k\) 个成绩。系统需要去掉一个最高分和一个最低分，将剩下的分数取平均，就得到这个学生的最后成绩。本题就要求你编写这个互评系统的算分模块。

输入格式：

输入第一行给出3个正整数 \(N\) \(（3 < N ≤10_{4}，学生总数）\) 、\(k\) \(（3 ≤ k ≤ 10，每份作业的评审数）\) 、\(M\) \(（≤ 20，需要输出的学生数）\) 。随后 \(N\) 行，每行给出一份作业得到的 \(k\) 个评审成绩（在区间 \([0, 100]\) 内），其间以空格分隔。

输出格式：

按非递减顺序输出最后得分最高的 \(M\) 个成绩，保留小数点后3位。分数间有1个空格，行首尾不得有多余空格。

输入样例：

6 5 3
88 90 85 99 60
67 60 80 76 70
90 93 96 99 99
78 65 77 70 72
88 88 88 88 88
55 55 55 55 55

输出样例：

87.667 88.000 96.000

解题思路

水题。就是要求比较多，需要求出最高的 \(m\) 个平均分并且按照非递减输出，我用的是大顶堆，然后取出前 \(m\) 个值放入栈中，再取出，这样就可以非递减输出了。

/*   一切都是命运石之门的选择  El Psy Kongroo  */
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<cmath>
#include<functional>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<double, double> pdd;
typedef pair<string, int> psi;
typedef __int128 int128;
#define PI acos(-1.0)
#define x first
#define y second
//int dx[4] = {1, -1, 0, 0};
//int dy[4] = {0, 0, 1, -1};
const int inf = 0x3f3f3f3f, mod = 1e9 + 7;

const int N = 1e4 + 10;
int n, m, k;
priority_queue<double> q;
double st[N];
int top = -1;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> k >> m;
    while(n -- ){
        int sum = 0, maxv = 0, minv = inf, v;
        for(int i = 0; i < k; i ++ ) 
            cin >> v, sum += v, maxv = max(maxv, v), minv = min(minv, v);
        sum -= maxv + minv;   //删除最高分和最低分

        double ave = sum * 1.0 / (k - 2);
        q.push(ave);
    }

    while(m -- ){   //求出前m个最高平均分
        st[ ++ top] = q.top();  
        q.pop();
    }

    while(top) printf("%.3lf ", st[top -- ]);
    printf("%.3lf\n", st[top]);

    return 0;
}