【NOIP2009 普及组】分数线划定

题目描述

世博会志愿者的选拔工作正在 A 市如火如荼的进行。为了选拔最合适的人才，A 市对所有报名的选手进行了笔试，笔试分数达到面试分数线的选手方可进入面试。面试分数线根据计划录取人数的 150% 划定，即如果计划录取 m 名志愿者，则面试分数线为排名第 m*150%（向下取整）名的选手的分数，而最终进入面试的选手为笔试成绩不低于面试分数线的所有选手。

现在就请你编写程序划定面试分数线，并输出所有进入面试的选手的报名号和笔试成绩。

输入格式

第一行，两个整数 n,m(5<=n<=5000,3<=m<=n)，中间用一个空格隔开，其中 n 表示报名参加笔试的选手总数，m 表示计划录取的志愿者人数。输入数据保证 m*150% 向下取整后小于等于 n。

第二行到第 n+1 行，每行包括两个整数，中间用一个空格隔开，分别是选手的报名号 k(1000<=k<=9999)和该选手的笔试成绩 s(1<=s<=100)。数据保证选手的报名号各不相同。

输出格式

第一行，有 2 个整数，用一个空格隔开，第一个整数表示面试分数线；第二个整数为进入面试的选手的实际人数。

从第二行开始，每行包含 2 个整数，中间用一个空格隔开，分别表示进入面试的选手的报名号和笔试成绩，按照笔试成绩从高到低输出，如果成绩相同，则按报名号由小到大的顺序输出。

样例 #1

样例输入 #1

样例输出 #1

我的代码

#include <stdio.h>
typedef struct Info{
    int id;
    int score;
} info;
void sort(info a[], int n) {
    int i, j, k, t1, t2;

    for (i = 0; i < n - 1; i++) {
        for (k = i, j = i + 1; j < n; j++) {
            // 首先按照分数降序排序
            if (a[j].score > a[k].score) {
                k = j;
            }
            // 如果分数相同，则按照ID升序排序
            else if (a[j].score == a[k].score && a[j].id < a[k].id) {
                k = j;
            }
        }

        if (k != i) {
            // 交换ID
            t1 = a[i].id;
            a[i].id = a[k].id;
            a[k].id = t1;

            // 交换分数
            t2 = a[i].score;
            a[i].score = a[k].score;
            a[k].score = t2;
        }
    }
}
int main(){
    int n,m;
    info a[5000]={0,0};
    scanf("%d %d",&n,&m);
    for (int i=0;i<n;i++){
        scanf("%d %d",&a[i].id,&a[i].score);
    }
    sort(a,n);
    int passnum=(int)(m*1.5),passscore=0,count=0;
    for (int i=0;i<n;i++,count++){
        if (passnum<=count&&a[i].score!=a[i-1].score){
            passscore=a[i-1].score;
            passnum=count;
            break;
        }
        
    }   
    printf("%d %d\n",passscore,passnum);
    for (int i=0;i<passnum;i++){
        printf("%d %d\n",a[i].id,a[i].score);
    }
    return 0;
}