BestCoder Round #59 (div.2) 1001 SDOI 模拟题

一年一度的全国信息学奥林匹克竞赛（NOI）即将举办，SD省组织进行了一次省队选拔，一共有 $n(n\le 100)$名选手参加了这次省队选拔。
今年，SD省的省队名额为 $m(m\le 50)$ 人，即，今年的SD省队有 $m$ 名队员。

按照惯例，SD省的省队选拔有两轮比赛，依次为“Round1”和“Round2”，每个Round的满分为 $300$ 分。
所有 n 名选手都参加了Round1和Round2，现在每名选手Round1和Round2的“原始得分”已经确定。SD省的省队选拔采用标准分计算方式，即，设某个Round的最高原始得分为 $x$ 分（保证每轮比赛都不会全场零分，即$x>0$），那么此Round每名选手的“相对得分”为: 这名选手此Round的原始得分$\ast (300/x)$。
所有选手的Round1和Round2的相对得分计算完毕后，将计算每名选手的“最终成绩”。一名选手的最终成绩为：这名选手的Round1相对得分$\ast 0.3$ + 这名选手的Round2相对得分$\ast 0.7$。非常和谐的是，保证不存在两名选手的最终成绩相等。

所有选手的最终成绩计算完毕后，将会按照以下规则选出省队队员：
为了鼓励女生参加信息学奥赛及相关活动，在有女选手参加省队选拔的情况下，省队中有一个固定的女选手名额。
1）若没有女选手参加省队选拔，则最终成绩最高的 $m$ 位选手进入省队。
2）若有女选手参加省队选拔，则最佳女选手（女选手中最终成绩最高者）进入省队，其余的选手（男选手和最佳女选手之外的女选手）中成绩最高的 $m-1$ 位选手进入省队。

现在已经到了省队选拔的最后阶段，请你编写一个程序，根据输入的所有选手的信息（姓名，性别，Round1和Round2的原始得分），输出进入省队的选手的姓名，输出的姓名按照省队队员的最终成绩降序（从高到低）排列。

第一行为一个整数 $T(T\le 100)$，表示数据组数。
接下来有$T$组数据。
对于每组数据，第一行有两个正整数 $n$ 和 $m(n\ge m)$，分别表示参加省队选拔的选手人数和省队的名额数。接下来有 $n$ 行，每行输入一名选手的信息，共4项，依次为姓名（一个长度不超过20的字符串，只包含数字和大小写英文字母）、性别（一个字符串，为"male"[男]或"female"[女]）、Round1原始得分（小于等于300的非负整数）和Round2原始得分（小于等于300的非负整数）。各项之间用空格隔开。

对于每组数据，先输出一行"The member list of Shandong team is as follows:"(不带引号),接下来输出$m$行，每行为一名省队队员的姓名，按省队队员的最终成绩降序（从高到低）排列。

2
10 8
dxy male 230 225
davidwang male 218 235
evensgn male 150 175
tpkuangmo female 34 21
guncuye male 5 15
faebdc male 245 250
lavender female 220 216
qmqmqm male 250 245
davidlee male 240 160
dxymeizi female 205 190
2 1
dxy male 300 300
dxymeizi female 0 0

The member list of Shandong team is as follows:
faebdc
qmqmqm
davidwang
dxy
lavender
dxymeizi
davidlee
evensgn
The member list of Shandong team is as follows:
dxymeizi

第一组数据：第一轮最高分为$250$,所以每个人的成绩都要乘$(300/250)=1.2$，第二轮最高分也为$250$,每个人的成绩也要乘$1.2$。
每个人的最终成绩按降序排如下
faebdc 298.20
qmqmqm 295.80
davidwang 275.88
dxy 271.80
lavender 260.64
dxymeizi 233.40
davidlee 220.80
evensgn 201.00
tpkuangmo 29.88
guncuye 14.40
有女选手参加，最佳女选手lavender进入省队，其他分最高的$7$人按名次排列进入省队

第二组数据：有女选手参加，最佳女选手dxymeizi进入省队，dxy虽然分高，但不能进队。

分析：先找出每个人的总分，然后按降序输出前m个即可。注意有女队员的情况。

实现代码如下：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
struct People
{
    char name[25],sex[10];
    int s1,s2;
    double s;
    bool operator <(const People &a) const
    {
        return s>a.s;
    }
}p[110];
int main()
{
    int t,n,m;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        int m1=0,m2=0;
        bool flag=false;
        for(int i=0;i<n;i++)
        {
            scanf("%s%s%d%d",p[i].name,p[i].sex,&p[i].s1,&p[i].s2);
            if(m1<p[i].s1) m1=p[i].s1;
            if(m2<p[i].s2) m2=p[i].s2;
            if(p[i].sex[0]=='f') flag=true;
        }
        for(int i=0;i<n;i++)
          p[i].s=p[i].s1*(300.0/m1)*0.3+p[i].s2*(300.0/m2)*0.7;
        sort(p,p+n);
        puts("The member list of Shandong team is as follows:");
        if(flag)
        {
            int z=0,i=0;
            bool first=true;
            for(;i<n;i++)
              if(p[i].sex[0]=='f') break;
            z=i;
            if(m>1)
            {
                if(z>=m)
                {
                    for(int j=0;j<m-1;j++)
                      printf("%s\n",p[j].name);
                    printf("%s\n",p[z].name);
                }
                else
                  for(int k=0;k<m;k++)
                    printf("%s\n",p[k].name);
            }
            else printf("%s\n",p[z].name);
        }
        else
          for(int i=0;i<m;i++)
            printf("%s\n",p[i].name);
    }
    return 0;
}