L2-015 互评成绩

标签：min int max 复杂度互评 num L2 015 sum

一、问题描述

二、问题分析

三、源码解答

四、时空复杂度分析

五、参考资料

一、问题描述

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

1. 输入格式

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

2. 输出格式

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

3. 输入样例

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

4. 输出样例

87.667 88.000 96.000

5. 限制条件

代码长度限制        16 KB

时间限制                300 ms

内存限制                64 MB

栈限制 8192 KB

二、问题分析

1. 数据结构选择：本题的最大数据已经给定，因此既可以定义一个数组又可以使用vector，因最后要求保留三位小数，因此数据类型选择高精度的double类型。

2. 去掉最大值和最小值：将最小值min_num初始化上限值100，将最大值max_num初始化下限值0，输入数据的同时比较最值，同时使用sum进行求和，最后用sum - max_num - min_num再取平均值。

3. 排序算法的选择：题目限制时间为300ms，最大数据N为 $10^4$ ，如果对所有数据进行排序，使用sort排序，时间复杂度为 $O(nlogn)$ ，经验证，不会超时。

但是有没有时间复杂度更小的选择呢？也是有的，因为题目只输出top-k个最高成绩，因此我们可以用小根堆q【优先队列】，该队列只维护k个元素，并且小值在顶。遇到一个新的成绩g：

$if(q.size() < k)$ $q.push(g)$ ;

$else if(q.top()<g)$ 移除 $q.top(), q.push(g)$ ；

$else$ 不做任何操作。

这样就能保持q中top-k元素为最大，并且每次压入或者移除的时间复杂度均为 $logk$ ，最坏情况下每次都需要更改顶部值，时间复杂度即为 $O(nlogk)$ ，而题目中 $k << n$ ，可以一定程度上节省时间。

三、源码解答

1. 使用sort直接排序

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define debug(a) cout << "Line " << __LINE__ << ":  " << #a << " = " << a << endl
#define FLOAT_FIXED(n) cout << setiosflags(ios::fixed) << setprecision(n)
int main() {
    IOS;
    //大的沉底
    vector<double>v;
    int n, m, k;
    cin >> n >> m >> k;
    int num;
    while(n--) {
        int sum = 0, min_num = 100, max_num = 0;
        for(int i = 1; i <= m; ++i) {
            cin >> num;
            if(num < min_num) min_num = num;
            if(num > max_num) max_num = num;
            sum += num;
        }
        double score = (sum - max_num - min_num) * 1.0 / (m - 2);
        v.push_back(score);
    }
    FLOAT_FIXED(3);
    sort(v.begin(), v.end(), greater<double>());
    for(int i = k - 1; i >= 0; --i) {
        cout << v[i];
        if(i) cout << " ";
    }
    return 0;
}

2. 使用优先队列

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define debug(a) cout << "Line " << __LINE__ << ":  " << #a << " = " << a << endl
#define FLOAT_FIXED(n) cout << setiosflags(ios::fixed) << setprecision(n)
int main() {
    IOS;
    //大的沉底
    priority_queue<double, vector<double>, greater<double>>pq;
    // vector<double>v;
    int n, m, k;
    cin >> n >> m >> k;
    int num;
    while(n--) {
        int sum = 0, min_num = 100, max_num = 0;
        for(int i = 1; i <= m; ++i) {
            cin >> num;
            if(num < min_num) min_num = num;
            if(num > max_num) max_num = num;
            sum += num;
        }
        double score = (sum - max_num - min_num) * 1.0 / (m - 2);
        // v.push_back(score);
        if(pq.size() < k) pq.push(score);
        else if(pq.top() < score) {
            pq.pop();
            pq.push(score);
        }
    }
    FLOAT_FIXED(3);
    // sort(v.begin(), v.end(), greater<double>());
    // for(int i = k - 1; i >= 0; --i) {
    //     cout << v[i];
    //     if(i) cout << " ";
    // }
    while(true) {
        cout << pq.top();
        pq.pop();
        if(pq.empty()) break;
        else cout << " ";
    }
    return 0;
}