博客

题目描述

天梯赛结束后，某企业的人力资源部希望组委会能推荐一批优秀的学生，这个整理推荐名单的任务就由静静姐负责。企业接受推荐的流程是这样的：

只考虑得分不低于 175 分的学生；
一共接受 K 批次的推荐名单；
同一批推荐名单上的学生的成绩原则上应严格递增；
如果有的学生天梯赛成绩虽然与前一个人相同，但其参加过 PAT 考试，且成绩达到了该企业的面试分数线，则也可以接受。

给定全体参赛学生的成绩和他们的 PAT 考试成绩，请你帮静静姐算一算，她最多能向企业推荐多少学生？

输入格式：

输入第一行给出 3 个正整数：N（≤105）为参赛学生人数，K（≤5×103）为企业接受的推荐批次，S（≤100）为该企业的 PAT 面试分数线。

随后 N 行，每行给出两个分数，依次为一位学生的天梯赛分数（最高分 290）和 PAT 分数（最高分 100）。

输出格式：

在一行中输出静静姐最多能向企业推荐的学生人数。

解题思路

有两个测试点运行超时，还没有想出来……

参考他人的代码，思想很容易理解，非常巧妙，具体详细代码可见


L1-8 静静的推荐 (20）,C语言，超级简单的代码哦，你不是不会，只是没细想而已

代码

//正确的代码
#include <stdio.h>
int main(){
    int arr[291] = {0}, brr[291] = {0};
    int n, k, s, cnt = 0, i, score, pscore;
    
    scanf("%d%d%d", &n, &k, &s);
    while (n--){
        scanf("%d%d", &score, &pscore);
        if (score >= 175){
            arr[score]++;
        }
        if (pscore >= s){
            brr[score]++;
        }
    }
    while (k--){
        for (i=175; i<291; i++){
            if (arr[i] > 0){
                cnt++;
                arr[i]--;
                while (arr[i]>0 && brr[i]>0){
                    cnt++;
                    arr[i]--;
                    brr[i]--;
                }
            }
        }
    }
    
    printf("%d", cnt);
    
    return 0;
}

//错误代码
#include <stdio.h>

struct stu
{
    int grade; // 天梯赛分数
    int pat;   // PAT分数
    int flag;  // 是否被推荐
};

int main()
{
    // input
    int n, k, s;
    scanf("%d%d%d", &n, &k, &s);
    struct stu st[n];
    for (int i=0; i<n; i++)
        scanf("%d%d", &st[i].grade, &st[i].pat);

    // process
    int cnt = 0; // 初始化要推荐的学生人数为0
    for (int i=0; i<n; i++)
        st[i].flag = 0; // 初始化学生全部未推荐
    
    // 参赛学生按照天梯赛成绩排序
    struct stu tmp;
    for (int i=0; i<n-1; i++){
        for (int j=i+1; j<n; j++){
            if (st[i].grade > st[j].grade){
                tmp = st[i];
                st[i] = st[j];
                st[j] = tmp;
            }
        }
    }

    for (int i=0; i<k; i++){
        int min = 0;
        for (int j=0; j<n; j++){
            if ((st[j].grade >= 175 && st[j].flag == 0
                && st[j].grade > min)
                || (st[j].grade == min && st[j].flag == 0
                && st[j].pat >= s)){
                cnt++; // 推荐人数加1
                st[j].flag = 1; // 修改标记位
                min = st[j].grade;
//                 printf("tuijian %d\n", st[j].grade);
            }
        }
    }

    // output
    printf("%d\n", cnt);

    return 0;
}

依旧是两个测试点显示运行超时，呜呜呜……

#include <stdio.h>

void swap(int * a, int * b){
    int tmp;
    
    tmp = *a;
    *a = *b;
    *b = tmp;
}

int main(){
    int n, k, s, i, j;
    int score = 0, cnt = 0;
    
    scanf("%d%d%d", &n, &k, &s);
    
    int arr[n][2];
    for (i=0; i<n; i++){
        scanf("%d %d", &arr[i][0], &arr[i][1]);
    }
    
    int brr[n];
    for (i=0; i<n; i++){
        brr[i] = 0;
    }
    for (i=0; i<n; i++){
        if (arr[i][0]>=175 && arr[i][1]>=s){
            brr[i] = 1;
        }
    }
    for (i=0; i<n-1; i++){
        if (brr[i] == 1){
            continue;
        }
        for (j=i+1; j<n; j++){
            if (brr[j] == 1){
                continue;
            }
            if (arr[i][0] > arr[j][0]){
                swap(&arr[i][0], &arr[j][0]);
                swap(&arr[i][1], &arr[j][1]);
            }
            if (arr[i][0] == arr[j][0]){
                if (arr[i][1] > arr[j][1]){
                    swap(&arr[i][1], &arr[j][1]);
                }
            }
        }
    }
    
    /*for (i=0; i<n; i++){
        printf("%d %d\n", arr[i][0], arr[i][1]);
    }
    printf("Next\n");*/
    
    for (i=0; i<k; i++){
        score = 0;
        for (j=0; j<n; j++){
            if (brr[j] == 1){
                continue;
            }
            if (arr[j][0] < 175){
                continue;
            }
            if (arr[j][0] > score){
                score = arr[j][0];
                brr[j] = 1;
//                printf("%d %d\n", arr[j][0], arr[j][1]);
                continue;
            }
            if (arr[j][0]==score && arr[j][1]>=s){
                brr[j] = 1;
//                printf("%d %d\n", arr[j][0], arr[j][1]);
            }
        }
    }
    for (i=0; i<n; i++){
        if (brr[i] == 1){
            cnt++;
        }
    }
    
    printf("%d", cnt);
    
    
    return 0;
}