Voldemort's blog

Voldemort's blog

我好菜啊

题解 AT858 【成績判定】

posted on 2020-09-09 19:37:13 | under 题解 |

Description

现在有 $a$ 门科目, $c$ 个人。每个人必须通过 $b$ 门科目才算及格,而至少需要 $d$ 个人及格。现在给出成绩表 $e_{i,j}$ 表示第 $i$ 个人在第 $j$ 门科目的得分。
(由于题目翻译太没用了,所以本蒟蒻自己翻译了一边,希望各位巨佬能看懂~)

Solution

看见题目的第一个反应就是排序,对于每一个人,我们把他的成绩降序排序后他的期望及格分就是 $e_{i,b}$ 。我们存下每一个 $e_{i,b}$ 并对其继续做一遍降序排序,记这一次存下来的数列存在 p 里,那么 $p_d$ 即为所求。

Code

#include <bits/stdc++.h>
using namespace std;

const int N = 109;

int f[N],p[N];  //对于每一组e,我们可以将其降维至一组数据f中
int a,b,c,d;
int ans;

bool cmp(int u,int v) { //注意是降序
    return u > v;
}

int main() {
    scanf("%d %d %d %d",&a,&b,&c,&d);
    for(int i = 1;i <= c;i++) {
        for(int j = 1;j <= a;j++) {
            scanf("%d",&f[j]);
        }
        sort(f + 1,f + a + 1,cmp);
        p[i] = f[b];
    }
    sort(p + 1,p + c + 1,cmp);
    printf("%d\n",p[d]);
    return 0;
}