题解 | 分数线划定(C语言)(快速排序法)

#include <stdio.h>

int should_move_right(int arrcj,int arrbmh,int pivot_cj,int pivot_bmh)
{
    if(arrcj != pivot_cj)
        return arrcj > pivot_cj;//按成绩降序
    else
        return arrbmh < pivot_bmh;//按报名号升序
}
void quick_sort(int arrcj[],int arrbmh[],int left,int right)
{
    if(left >= right) return;//递归结束条件
    int pivot_cj = arrcj[left];
    int pivot_bmh = arrbmh[left];
    int l = left;
    int r = right;
    while(l < r)
    {
        while(l < r && !should_move_right(arrcj[r],arrbmh[r],pivot_cj,pivot_bmh))
            r--;
        if(l < r)
        {
            arrcj[l] = arrcj[r];
            arrbmh[l] = arrbmh[r];
            l++;
        }
        while(l < r && should_move_right(arrcj[l],arrbmh[l],pivot_cj,pivot_bmh))
            l++;
        if(l < r)
        {
            arrcj[r] = arrcj[l];
            arrbmh[r] = arrbmh[l];
            r--;
        }
    }
    arrcj[l] = pivot_cj;
    arrbmh[l] = pivot_bmh;
    quick_sort(arrcj,arrbmh,left,l-1);
    quick_sort(arrcj,arrbmh,r+1,right);
}
int main() {
    int n,m;
    scanf("%d %d",&n,&m);
    int arrbmh[n],arrcj[n];
    int i;
    for(i=0;i<n;i++) scanf("%d %d",&arrbmh[i],&arrcj[i]);

    quick_sort(arrcj,arrbmh,0,n-1);//排序

    int t = m*1.5;
    int line = arrcj[t-1];//分数线，第t个人的分数，在数组中对应的下标应该减一
    int cnt = 0;
    //统计分数大于等于分数线的人数（进入面试的人数）
    for(i=0;i<n;i++)
    {
        if(arrcj[i] >= line)
            cnt++;
    }
    //最终输出
    printf("%d %d\n",line,cnt);
    for(i=0;i<cnt;i++)
        printf("%d %d\n",arrbmh[i],arrcj[i]);
    return 0;
}