题解 P1068 【分数线划定】

· · 题解

这道题本质就是排序，分数高的优先，人数够了就划分数线，把同分的也算进来就行了。

其实这道题不要求你把全部数排序，堆排会快，桶排……

算一下，快排堆排n log n复杂度5000×5000 log2≤5000×13=65000

桶排是要看你怎么排了……

你可以强行开布尔数组存每一个序号与每一个成绩的对应，100×8999=899900这是慢一些的，但也可以过（冒泡都能过）

也可以用真正的计数排序，当当当！开一堆链表（或vector）存每一个成绩的序号，每个序号内部排序，其实也是很快的。

我图简单，用了模板库sort（快排）

我没有用结构体，用了一个编码存成绩与序号

由于先由大到小排成绩由小到大排序号

可以这样存：

有人成绩s，序号k，

则编码a=s×10000+10000-k

由于1000 ≤ k ≤ 9999 < 10000，其编码顺序肯定先由成绩决定

而由于序号是由小到大排序，与成绩相反，我就取其与10000的差，序号的从小到大就变为与成绩相同的从大到小了

编码的思想在很多题都有用

附代码

    #include<cstdio>
    #include<algorithm>
    using namespace std;
    int a[5001];
    int main()
    {
        int n,m,i,s,k;
        scanf("%d %d",&n,&m);
        m+=m>>1;
        for (i=0;i<n;i++)
            scanf("%d %d",&k,&s),a[i]=s*10000+10000-k;
        sort(a,a+n);
        for (i=n-m-1;i>=0;i--)
            if (a[n-m]/10000>a[i]/10000)
                break;
        printf("%d %d\n",a[n-m]/10000,n-i-1);
        for (k=n-1;k>i;k--)
            printf("%d %d\n",10000-a[k]%10000,a[k]/10000);
        return 0;
}