NOIP 2009 分数线划定

深藏阁楼爱情的钟 2022-05-16 02:09 377阅读 0赞

题目描述

世博会志愿者的选拔工作正在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）。数据保证选手的报名号各不相同。

输出

每组输出的第一行，有两个整数，用一个空格隔开，第一个整数表示面试分数线；第二个整数为进入面试的选手的实际人数。   
从第二行开始，每行包含两个整数，中间用一个空格隔开，分别表示进入面试的选手的报名号和笔试成绩，按照笔试成绩从高到低输出，如果成绩相同，则按报名号由小到大的顺序输出。   
  
  
下面是对样例数据的解释：

m\*150%=3\*150%=4.5，向下取整后为4。保证4个人进入面试的分数线为88，但因为88有重分，所以所有成绩大于等于88的选手都可以进入面试，故最终有5 个人进入面试。

分析：首先利用结构体排序，将这些人的笔试成绩从高到低排序，同分的时候按照报名号从小到大排序，记录取人数的150%的人数为x，因为题目说如果后面有与第x名的人同分的时候，这些同分的人也会进入面试，所以直接将下标为x的人的成绩设置为分数线，看后面是否有人与分数线同分，如果有，则让录取人数++，最后输出即可。

#include<map>
    #include<set>
    #include<cmath>
    #include<queue>
    #include<stack>
    #include<cstdio>
    #include<vector>
    #include<cctype>
    #include<cstring>
    #include<utility>
    #include<cstdlib>
    #include<iomanip>
    #include<iostream>
    #include<algorithm>
    #define Clear(x) memset(x,0,sizeof(x))
    #define fup(i,a,b) for(int i=a;i<b;i++)
    #define rfup(i,a,b) for(int i=a;i<=b;i++)
    #define fdn(i,a,b) for(int i=a;i>b;i--)
    #define rfdn(i,a,b) for(int i=a;i>=b;i--)
    typedef long long ll;
    typedef unsigned long long ull;
    using namespace std;
    const int maxn=5e3+7;
    
    struct node{
        int k,s;
        bool operator < (const node&a)const
        {
            if(s!=a.s) return s>a.s;
            return k<a.k;
        }
    }a[maxn];
    
    int read()
    {
        char ch=getchar();int ret=0,f=1;
        while(ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
        while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
        return f*ret;
    }
    
    int main()
    {
        int n=read(),m=read();
        rfup(i,1,n)
            a[i].k=read(),a[i].s=read();
        sort(a+1,a+1+n);
        int cnt=floor(m*1.5);//向下取整
        int line=a[cnt].s,people=cnt;
        rfup(i,cnt+1,n)
        {
            if(a[i].s==line){
                people++;
            }
            else break;
        }
        printf("%d %d\n",line,people);
        rfup(i,1,people)
            printf("%d %d\n",a[i].k,a[i].s);
        return 0;
    }