分数线划定

题意

根据计划录取人数的 $150\%$ 确定面试分数线，并输出所有分数不低于分数线的选手。成绩相同的选手按报名号升序输出。

思路

先按 (-分数, 报名号) 排序。分数线是第 int(m * 1.5) 名的成绩，对应 Python 下标 int(m * 1.5) - 1。再从排好序的序列中筛出所有分数不低于这条线的选手，自然保持题目要求的输出顺序。

代码

Python代码

python

1
2
3
4
5
6
7
8
9
10
11student_count, planned_count = map(int, input().split())
candidates = [tuple(map(int, input().split())) for _ in range(student_count)]

candidates.sort(key=lambda candidate: (-candidate[1], candidate[0]))
cutoff_index = int(planned_count * 1.5) - 1
cutoff_score = candidates[cutoff_index][1]
qualified = [candidate for candidate in candidates if candidate[1] >= cutoff_score]

print(cutoff_score, len(qualified))
for candidate_id, score in qualified:
    print(candidate_id, score)

C++代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73#include <cstdio>

int n ,m;
struct _s {
    int id;
    int val;
};

_s s[5005];

// >=
bool greater(_s &a, _s &b){
    if( a.id == b.id)
        return 1;
    if( a.val > b.val )
        return 1;
    else if ( a.val == b.val && a.id < b.id)
        return 1;
    return 0;
}
void xchg(_s &a,_s &b){
    _s t = a;
    a = b;
    b = t;
}

void quick_sort(int l,int r){
    if( l >= r) return ;

    int i = l,j = r;
    _s key = s[l];

    while( i != j){
        while(greater(key,s[j]) && i<j )
            j--;
        while( greater(s[i],key) && i < j)
            i++;
        if( i < j){
            xchg(s[i], s[j]);
        }
    }
    s[l] = s[i];
    s[i] = key;
    quick_sort(l, i-1);
    quick_sort(i+1,r);
}

void init(){
    scanf("%d%d",&n,&m);
    int i;
    for (i=1;i<=n;i++){
        scanf("%d%d",&s[i].id,&s[i].val);
    }
    m = (int)(m * 1.5);
}


int main(){
    init();
    quick_sort(1, n);
    int i;
    int fen = s[m].val;

    for (i=m+1;i<=n;i++){
        if( fen == s[i].val)
            m++;
    }
    printf("%d %d\n",s[m].val,m);
    for (i=1;i<=m;i++){
        printf("%d %d\n",s[i].id,s[i].val);
    }
    return 0;
}

复杂度

时间复杂度为 $O(n \log n)$ ，空间复杂度为 $O(n)$ 。

总结

分数线只决定最低分数，和分数线相同的所有选手都必须保留。

目录

题意

思路

代码

Python代码

C++代码

复杂度

总结