2018 团队设计天梯赛题解---华山论剑组

小鱼儿 2022-05-28 10:41 445阅读 0赞

## 写在前面 ##

2018 年度的团队设计天梯赛前几天结束了。但是成绩真的是惨不忍睹。。。毕竟是团队的比赛，如果团队平均水平不高的话，单凭一个人，分再高也很难拉起来（当然，一个人能单挑一个队的大神除外）。

说实话吧，其实这段话原本不想写，一个是团队成绩并不好，另一个也是自己发挥的也不好，没有达到目标分数。但是想想不管怎样都是一种经历，所以还是写了这段话。  
总结一下其实很多题放在平时做的话其实并不难，关键是心得放下来。但是一到比赛的氛围就不一样了，周围全是别的学校的大牛，又加上有时间限制和周围的一堆监考人员围着走，想要放平心态其实是不容易的。这种东西还真得多经历才会有感觉。好了，今天写了一部分的题，来记录下题解：

## L1-1 天梯赛座位分配（20 分） ##

天梯赛每年有大量参赛队员，要保证同一所学校的所有队员都不能相邻，分配座位就成为一件比较麻烦的事情。为此我们制定如下策略：假设某赛场有 N 所学校参赛，第 i 所学校有 M\[i\] 支队伍，每队 10 位参赛选手。令每校选手排成一列纵队，第 i+1 队的选手排在第 i 队选手之后。从第 1 所学校开始，各校的第 1 位队员顺次入座，然后是各校的第 2 位队员…… 以此类推。如果最后只剩下 1 所学校的队伍还没有分配座位，则需要安排他们的队员隔位就坐。本题就要求你编写程序，自动为各校生成队员的座位号，从 1 开始编号。

输入格式：

输入在一行中给出参赛的高校数 N （不超过100的正整数）；第二行给出 N 个不超过10的正整数，其中第 i 个数对应第 i 所高校的参赛队伍数，数字间以空格分隔。

输出格式：

从第 1 所高校的第 1 支队伍开始，顺次输出队员的座位号。每队占一行，座位号间以 1 个空格分隔，行首尾不得有多余空格。另外，每所高校的第一行按“\#X”输出该校的编号X，从 1 开始。

输入样例：
    3
    3 4 2
    输出样例：
    #1
    1 4 7 10 13 16 19 22 25 28
    31 34 37 40 43 46 49 52 55 58
    61 63 65 67 69 71 73 75 77 79
    #2
    2 5 8 11 14 17 20 23 26 29
    32 35 38 41 44 47 50 53 56 59
    62 64 66 68 70 72 74 76 78 80
    82 84 86 88 90 92 94 96 98 100
    #3
    3 6 9 12 15 18 21 24 27 30
    33 36 39 42 45 48 51 54 57 60

第一题其实意思不难理解，就是坑有点多，思路就是模拟题意去做就行了。普遍的坑就是第二个测试点和第三个测试点。  
**对于第二个测试点过不了的情况，可以试试下面的输入数据：**

2
    5 1

如果结果对了，第二个测试点也就过了。  
**对于第三个测试点可以试试只有一个学校的情况：**

1
    2

最后是 AC 代码：

/**
     * 先分配第一个学校第一个队的第一个队员，再分配第二个学校的第一个队的第一个队员，
     * 再分配第三个学校的第一个队的第一个队员... 最后一个学校的第一个队的最后一个队员。 
     * 所有学校的第一个队分配完毕，接下来是第一个学校的第二个队的第一个队员，
     * 第二个学校的第二个队的第一个队员，第三个学校的第二个队的第一个队员... 
     */ 
    #include <iostream>
    using namespace std;
    
    const int MAXN = 110;
    int schoolNum[MAXN]; // 记录每个学校的队数 
    int peo[MAXN][10][10]; // 记录每个队员的编号 
    
    int main() {
        int n;
        int maxx = 0;
        cin >> n;
        for (int i = 0; i < n; i++) {
            scanf("%d", schoolNum + i);
            maxx = max(maxx, schoolNum[i]);
        }
        int t, lastSchool = -1; // 上一次分配位置的队员所在的学校 
        int startPos = 0; // 开始位置 
        for (int j = 0; j < maxx; j++) { // 第 j 个队 
            for (int k = 0; k < 10; k++) { // 每个队 10 个人 
                for (int i = 0; i < n; i++) { // n 个学校 
                    if (schoolNum[i] <= j) {
                        continue;
                    }
                    // 如果上一次分配位置的队员和现在分配位置的队员在同一个学校
                    // 那么证明是同一所学校的队员，需要间隔一个位置。 
                    if (lastSchool == i) {
                        startPos += 2;
                    } else { // 否则证明是不同的学校的队员，相邻座就好 
                        startPos++;
                    }
                    peo[i][j][k] = startPos;
                    lastSchool = i; // 更新上一次分配位置的队员所在的学校 
                }
            }
        }
        for (int i = 0; i < n; i++) {
            cout << "#" << (i+1) << endl;
            for (int j = 0; j < schoolNum[i]; j++) {
                for (int k = 0; k < 10; k++) {
                    if (k) {
                        cout << " ";
                    }
                    cout << peo[i][j][k];
                }
                cout << endl;
            }
        }
    
        return 0;
    }

## L1-2 倒数第N个字符串（15 分） ##

给定一个完全由小写英文字母组成的字符串等差递增序列，该序列中的每个字符串的长度固定为 L，从 L 个 a 开始，以 1 为步长递增。例如当 L 为 3 时，序列为 \{ aaa, aab, aac, …, aaz, aba, abb, …, abz, …, zzz \}。这个序列的倒数第27个字符串就是 zyz。对于任意给定的 L，本题要求你给出对应序列倒数第 N 个字符串。

输入格式：

输入在一行中给出两个正整数 L（2 ≤ L ≤ 6）和 N（≤10  
5  
）。

输出格式：

在一行中输出对应序列倒数第 N 个字符串。题目保证这个字符串是存在的。

输入样例：
    3 7417
    输出样例：
    pat

**这个其实类似于给出一个整数 `x`，再给出一个数 `n` ，然后求出 `x` 一直往前减 1 ，直到减了 `n - 1`次的值（因为 `x` 本身是倒数第一个数，所以只需减 `n - 1` 次）。**  
对于字符串也是一样的。**比如：`zzz` 的前一个字符串就是 `zzy` ，`zza` 的前一个字符串就是 `zyz` 。**所以我们只需要对一个字符串模拟整数的自减就可以了。下面是 AC 代码：

/**
     * 用字符串模拟整数的自减过程
     */
    #include <iostream>
    #include <string>
    using namespace std;
    
    int main() {
      int n, m;
      cin >> n >> m;
      string str;
      // 构造最末尾的字符串
      for (int i = 0; i < n; i++) {
        str.append(1, 'z');
      }
      int size = str.length();
      // 减 m-1 次，因为 str 是倒数第一个字符串 
      for (int i = 0; i < m-1; i++) {
        for (int j = size-1; j >= 0; --j) {
          if (str[j] > 'a') {
            str[j]--;
            // 将当前字符后面的所有字符置为 'z'，例：zza 的前一个字符串为 zyz
            for (int t = j+1; t < size; t++) {
              str[t] = 'z';
            }
            break;
          }
        }
      }
      cout << str << endl;
    
      return 0;
    }

## L1-3 打折（5 分） ##

去商场淘打折商品时，计算打折以后的价钱是件颇费脑子的事情。例如原价 ￥988，标明打 7 折，则折扣价应该是 ￥988 x 70% = ￥691.60。本题就请你写个程序替客户计算折扣价。

输入格式：

输入在一行中给出商品的原价（不超过1万元的正整数）和折扣（为\[1, 9\]区间内的整数），其间以空格分隔。

输出格式：

在一行中输出商品的折扣价，保留小数点后 2 位。

输入样例：
    988 7
    输出样例：
    691.60

这个题目没啥讲的，注意下把第二个整数转换成浮点数就好了，因为 `整数 / 整数 = 整数`

#include <iostream>
    using namespace std;
    
    int main() {
      int n;
      double m;
      cin >> n >> m;
      printf("%.2lf", n*m/10);
      return 0;
    }

## L1-4 2018我们要赢（5 分） ##

2018年天梯赛的注册邀请码是“2018wmyy”，意思就是“2018我们要赢”。本题就请你用汉语拼音输出这句话。

输入格式：

本题没有输入。

输出格式：

在第一行中输出：“2018”；第二行中输出：“wo3 men2 yao4 ying2 !”。

输入样例：
    本题没有输入。
    输出样例：
    2018
    wo3 men2 yao4 ying2 !

代码：

#include <iostream>
    using namespace std;
    
    int main() {
      cout << "2018\nwo3 men2 yao4 ying2 !" << endl;
    }

## L1-5 电子汪（10 分） ##

据说汪星人的智商能达到人类 4 岁儿童的水平，更有些聪明汪会做加法计算。比如你在地上放两堆小球，分别有 1 只球和 2 只球，聪明汪就会用“汪！汪！汪！”表示 1 加 2 的结果是 3。

本题要求你为电子宠物汪做一个模拟程序，根据电子眼识别出的两堆小球的个数，计算出和，并且用汪星人的叫声给出答案。

输入格式：

输入在一行中给出两个 \[1, 9\] 区间内的正整数 A 和 B，用空格分隔。

输出格式：

在一行中输出 A + B 个Wang!。

输入样例：
    2 1
    输出样例：
    Wang!Wang!Wang!

这个也没有什么讲的，代码：

#include <iostream>
    using namespace std;
    
    int main() {
      int a, b;
      cin >> a >> b;
      a += b;
      for (int i = 0; i < a; i++) {
        cout << "Wang!";
      }
      return 0;
    }

## L1-6 福到了（15 分） ##

“福”字倒着贴，寓意“福到”。不论到底算不算民俗，本题且请你编写程序，把各种汉字倒过来输出。这里要处理的每个汉字是由一个 N × N 的网格组成的，网格中的元素或者为字符 @ 或者为空格。而倒过来的汉字所用的字符由裁判指定。

输入格式：

输入在第一行中给出倒过来的汉字所用的字符、以及网格的规模 N （不超过100的正整数），其间以 1 个空格分隔；随后 N 行，每行给出 N 个字符，或者为 @ 或者为空格。

输出格式：

输出倒置的网格，如样例所示。但是，如果这个字正过来倒过去是一样的，就先输出bu yong dao le，然后再用输入指定的字符将其输出。

输入样例 1：
    $ 9
     @  @@@@@
    @@@  @@@ 
     @   @ @ 
    @@@  @@@ 
    @@@ @@@@@
    @@@ @ @ @
    @@@ @@@@@
     @  @ @ @
     @  @@@@@
    输出样例 1：
    $$$$$  $ 
    $ $ $  $ 
    $$$$$ $$$
    $ $ $ $$$
    $$$$$ $$$
     $$$  $$$
     $ $   $ 
     $$$  $$$
    $$$$$  $
    输入样例 2：
    & 3
    @@@
     @ 
    @@@
    输出样例 2：
    bu yong dao le
    &&&
     & 
    &&&

通过测试样例可以发现：其输出的时候是将输入的字符串**上下顺序颠倒、左右顺序颠倒输出**。  
那么如果输入的 `n` 行字符串中，第 `i` 行和第 `n-i` 行是一样的，并且第 `i` 行是一个回文字符串（第 `x` 个字符和第 `m-x` 个字符相等。`m` 为字符串长度）。那么就可以输出不用倒了。  
AC代码：

#include <iostream>
    #include <vector>
    #include <string>
    using namespace std; 
    
    // 判断某个字符串是否是回文字符串 
    bool isHuiwen(string &str) {
        int len = str.length();
        for (int i = 0; i < len/2; ++i) {
            if (str[i] != str[len-1-i]) {
                return false;
            }
        }
        return true;
    }
    
    // 判断某个样例是否是不用倒了 
    bool judge(vector<string> &vec) {
        int size = vec.size();
        for (int i = 0; i < size/2; i++) {
            // 如果第 i 行字符串和倒数第 i 行字符串不相等
            // 或者第 i 行字符串不是回文字符串，那么返回 false 
            if (vec[i] != vec[size-1-i] || isHuiwen(vec[i]) == false) {
                return false;
            }
        } 
        return true;
    } 
    
    int main() {
        char c;
        int n;
        vector<string> vec; // 储存每行字符串的动态数组 
        vec.clear(); 
        cin >> c >> n;
        getchar(); // 耗掉输入缓冲区中的换行符
    
        for (int i = 0; i < n; i++) {
            string str;
            getline(cin, str);
            vec.push_back(str);
        } 
    
        // 判断是否不用倒了 
        if (judge(vec)) {
            cout << "bu yong dao le" << endl;
        }
        // 倒过来输出 
        int size = vec.size();
        int len;
        for (int i = size - 1; i >= 0; --i) {
            len = vec[i].length();
            for (int j = len - 1; j >= 0; --j) {
                if (vec[i][j] != ' ') {
                    cout << c;
                } else {
                    cout << ' ';
                }
            }
            cout << endl;
        }
    
        return 0;
    }

## L1-7 谁是赢家（10 分） ##

某电视台的娱乐节目有个表演评审环节，每次安排两位艺人表演，他们的胜负由观众投票和 3 名评委投票两部分共同决定。规则为：如果一位艺人的观众票数高，且得到至少 1 名评委的认可，该艺人就胜出；或艺人的观众票数低，但得到全部评委的认可，也可以胜出。节目保证投票的观众人数为奇数，所以不存在平票的情况。本题就请你用程序判断谁是赢家。

输入格式：

输入第一行给出 2 个不超过 1000 的正整数 Pa 和 Pb，分别是艺人 a 和艺人 b 得到的观众票数。题目保证这两个数字不相等。随后第二行给出 3 名评委的投票结果。数字 0 代表投票给 a，数字 1 代表投票给 b，其间以一个空格分隔。

输出格式：

按以下格式输出赢家：

The winner is x: P1 + P2  
其中 x 是代表赢家的字母，P1 是赢家得到的观众票数，P2 是赢家得到的评委票数。

输入样例：
    327 129
    1 0 1
    输出样例：
    The winner is a: 327 + 1

根据题目意思做就好了：

#include <iostream>
    using namespace std;
    
    int main() {
      int a, b;
      int aa, bb, cc;
      cin >> a >> b >> aa >> bb >> cc;
      if (a > b && aa+bb+cc < 3) {
        printf("The winner is %c: %d + %d\n", 'a', a, 3-aa-bb-cc);
      } else if (b > a && aa+bb+cc > 0) {
        printf("The winner is %c: %d + %d\n", 'b', b, aa+bb+cc);
      } else if (a < b && aa+bb+cc == 0) {
        printf("The winner is %c: %d + %d\n", 'a', a, 3);
      } else if (b < a && aa+bb+cc == 3) {
        printf("The winner is %c: %d + %d\n", 'b', b, 3);
      }
      return 0;
    }

## L1-8 猜数字（20 分） ##

一群人坐在一起，每人猜一个 100 以内的数，谁的数字最接近大家平均数的一半就赢。本题就要求你找出其中的赢家。

输入格式：

输入在第一行给出一个正整数N（≤10  
4  
）。随后 N 行，每行给出一个玩家的名字（由不超过8个英文字母组成的字符串）和其猜的正整数（≤ 100）。

输出格式：

在一行中顺序输出：大家平均数的一半（只输出整数部分）、赢家的名字，其间以空格分隔。题目保证赢家是唯一的。

输入样例：
    7
    Bob 35
    Amy 28
    James 98
    Alice 11
    Jack 45
    Smith 33
    Chris 62
    输出样例：
    22 Amy

对于这道题，用 STL 中的 map 结构去处理会比较方便，当然，C语言是没有 STL 的，那么我们可以用一个结构体，结构体里面有一个 `char` 型数组，用来保存每个人的名字，然后是一个 `int` 型变量，用来保存每个人猜的数字。  
之后定义一个该结构体数组，表示所有的人的信息。最后对这个结构体数组中的信息进行读取就好了。

这里用的 C++ STL 中的 map 做的，代码：

#include <iostream>
    #include <string>
    #include <map>
    #include <cmath>
    using namespace std;
    
    int main() {
      int n;
      cin >> n;
      string name;
      int num;
      int sum = 0;
      map<string, int> res; // 名字--分数  键值对
    
      for (int i = 0; i < n; i++) {
        cin >> name >> num;
        res[name] = num;
        sum += num;
      }
      sum /= (n*2);
    
      int close_ = 100;
      map<string, int>::iterator it = res.begin();
      map<string, int>::iterator resIndex = res.begin();
      for (; it != res.end(); ++it) {
        if (close_ > abs(it->second - sum)) {
          close_ = abs(it->second - sum);
          resIndex = it;
        }
      }
    
      cout << sum << " " << resIndex->first << endl;
    
      return 0;
    }

## L2-1 分而治之（25 分） ##

分而治之，各个击破是兵家常用的策略之一。在战争中，我们希望首先攻下敌方的部分城市，使其剩余的城市变成孤立无援，然后再分头各个击破。为此参谋部提供了若干打击方案。本题就请你编写程序，判断每个方案的可行性。

输入格式：

输入在第一行给出两个正整数 N 和 M（均不超过10 000），分别为敌方城市个数（于是默认城市从 1 到 N 编号）和连接两城市的通路条数。随后 M 行，每行给出一条通路所连接的两个城市的编号，其间以一个空格分隔。在城市信息之后给出参谋部的系列方案，即一个正整数 K （≤ 100）和随后的 K 行方案，每行按以下格式给出：

Np v\[1\] v\[2\] … v\[Np\]  
其中 Np 是该方案中计划攻下的城市数量，后面的系列 v\[i\] 是计划攻下的城市编号。

输出格式：

对每一套方案，如果可行就输出YES，否则输出NO。

输入样例：
    10 11
    8 7
    6 8
    4 5
    8 4
    8 1
    1 2
    1 4
    9 8
    9 1
    1 10
    2 4
    5
    4 10 3 8 4
    6 6 1 7 5 4 9
    3 1 8 4
    2 2 8
    7 9 8 7 6 5 4 2
    输出样例：
    NO
    YES
    YES
    NO
    NO

这题比赛的时候没看清题意，真的是可惜。  
**其实题目就是给你一个图的边的信息，之后每次给你若干个节点，当把这些节点和其他节点相连的边都去除之后（即为题目中的攻破该城市），判断这个图是否还有任意一条边相连（是否每个城市都是孤立的），如果有，那么证明方案不可行，否则方案可行。**

**需要注意的是如果采用二维数组储存图的信息，最后两个测试点是会内存超限的，另一种方法是用结构体储存边的信息，这样就不需要使用二维数组了。**

/**
     * 用二维数组储存图，最后两个测试点内存超限！！ 
     */ 
    /**
    #include <iostream>
    #include <vector>
    #include <cstring> 
    using namespace std;
    
    const int MAXN = 1e4+10; 
    int edge[MAXN][MAXN];
    
    int main() {
        int n, m;
        cin >> n >> m;
        int start, end;
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &start, &end);
            // 初始状态如果两个城市有边相连标记为 1 
            edge[start][end] = edge[end][start] = 1;
        }
        int k, num, t;
        cin >> k;
        int nodeCount;
        for (int i = 0; i < k; i++) {
            scanf("%d", &num);
            nodeCount = 0;
            for (int j = 0; j < num; j++) {
                scanf("%d", &t);
                for (int l = 1; l <= n; l++) {
                    // 攻破该城市，将所有和该城市相连的边置为 -1，
                    // 标记为已经攻破并孤立该城市 
                    if (edge[t][l] == 1) {
                        edge[t][l] = edge[l][t] = -1;
                    }
                }
            }
    
            bool canFinish = true;
            for (int l = 1; l <= n; l++) {
                for (int j = 1; j <= n; j++) {
                    // 如果发现不同城市之间有任何一条边相连，
                    // 那么证明这个方案是失败的 
                    if (edge[l][j] == 1) {
                        canFinish = false;
                    } else if (edge[l][j] == -1) { // 复原图，以便下次使用 
                        edge[l][j] = 1;
                    }
                }
            }
            if (canFinish) {
                cout << "YES" << endl;
            } else {
                cout << "NO" << endl;
            }
        }
    
        return 0;
    }
    */
    
    /**
     * 用结构体来保存边的信息，AC
     */
    #include <iostream>
    #include <cstring>
    using namespace std;
    
    const int MAXN = 1e4+10;
    
    struct Edge {
        int x, y;
    }; 
    
    Edge edge[MAXN];
    bool mark[MAXN]; // 标记节点是否被攻破 
    
    int main() {
        int n, m;
        cin >> n >> m;
        int start, end;
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &start, &end);
            edge[i].x = start;
            edge[i].y = end;
        }
        int k, num, t;
        bool canFinish;
        cin >> k;
        for (int i = 0; i < k; i++) {
            canFinish = true;
            // 复原节点为未被攻破状态
            memset(mark, 0, sizeof(bool)*MAXN);
            scanf("%d", &num);
            for (int j = 0; j < num; j++) {
                scanf("%d", &t);
                mark[t] = true; // 节点 t 被攻破 
            }
            // 遍历每一条边，如果某条边的两个顶点都没被攻破，
            // 证明这个方案是不行的 
            for (int i = 0; i < m; i++) {
                if (mark[edge[i].x] == false && mark[edge[i].y] == false) {
                    canFinish = false;
                    break;
                }
            }
            if (!canFinish) {
                cout << "NO" << endl;
            } else {
                cout << "YES" << endl;
            }
        }
    
    }

## L2-2 小字辈（25 分） ##

L2-2 小字辈（25 分）  
本题给定一个庞大家族的家谱，要请你给出最小一辈的名单。

输入格式：

输入在第一行给出家族人口总数 N（不超过 100 000 的正整数） —— 简单起见，我们把家族成员从 1 到 N 编号。随后第二行给出 N 个编号，其中第 i 个编号对应第 i 位成员的父/母。家谱中辈分最高的老祖宗对应的父/母编号为 -1。一行中的数字间以空格分隔。

输出格式：

首先输出最小的辈分（老祖宗的辈分为 1，以下逐级递增）。然后在第二行按递增顺序输出辈分最小的成员的编号。编号间以一个空格分隔，行首尾不得有多余空格。

输入样例：
    9
    2 6 5 5 -1 5 6 4 7
    输出样例：
    4
    1 9

**这题其实就是通过给定的输入数据建立一颗多叉树，然后从祖先开始往下遍历，找到最小的辈数和处于最小辈的人的编号。**  
具体看代码吧：

/**
     * 用数组来储存建立的多叉树
     */
    #include <vector>
    #include <iostream>
    using namespace std;
    
    const int MAXN = 1e5+10;
    const int ROOT_INDEX = 1e5+1; // 祖先所在数组下标 
    
    struct Peo {
        vector<int> children;
    };
    Peo peo[MAXN]; // 保存下标对应人的所有孩子编号 
    
    int minnChild; // 保存最小的辈数 
    vector<int> res; // 保存处于最小辈的人的编号  
    
    // 获取最小辈数 
    void getMinnChild(int index, int currentMinn) {
        int size = peo[index].children.size();
        if (size == 0) {
            // 如果这个人没有孩子，证明其可能是处于最小辈 
            minnChild = max(currentMinn, minnChild);
            return ;
        }
        for (int i = 0; i < size; i++) {
            getMinnChild(peo[index].children[i], currentMinn+1);
        }
    } 
    
    // 获取处于最小辈的人的编号 
    void solve(int index, int currentBei) {
        int size = peo[index].children.size();
        if (size == 0) {
            // 最小辈一定没有孩子，并且其所处的辈数等于最小辈数
            if (currentBei == minnChild) {
                res.push_back(index);
            }
            return ;
        }
        for (int i = 0; i < size; i++) {
            solve(peo[index].children[i], currentBei+1);
        }
    }
    
    int main() {
        int n, t;
        cin >> n;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &t);
            if (t == -1) {
                t = ROOT_INDEX;
            } 
            peo[t].children.push_back(i);
        } 
        // 从祖先开始遍历
        getMinnChild(ROOT_INDEX, 0);
        solve(ROOT_INDEX, 0);
    
        // 输出
        cout << minnChild << endl;
        int size = res.size();
        for (int i = 0; i < size; i++) {
            if (i) {
                cout << " ";
            }
            cout << res[i]; 
        }
    
        return 0;
    }

## L2-3 名人堂与代金券（25 分） ##

对于在中国大学MOOC（[http://www.icourse163.org/][http_www.icourse163.org] ）学习“数据结构”课程的学生，想要获得一张合格证书，总评成绩必须达到 60 分及以上，并且有另加福利：总评分在 \[G, 100\] 区间内者，可以得到 50 元 PAT 代金券；在 \[60, G) 区间内者，可以得到 20 元PAT代金券。全国考点通用，一年有效。同时任课老师还会把总评成绩前 K 名的学生列入课程“名人堂”。本题就请你编写程序，帮助老师列出名人堂的学生，并统计一共发出了面值多少元的 PAT 代金券。

输入格式：

输入在第一行给出 3 个整数，分别是 N（不超过 10 000 的正整数，为学生总数）、G（在 (60,100) 区间内的整数，为题面中描述的代金券等级分界线）、K（不超过 100 且不超过 N 的正整数，为进入名人堂的最低名次）。接下来 N 行，每行给出一位学生的账号（长度不超过15位、不带空格的字符串）和总评成绩（区间 \[0, 100\] 内的整数），其间以空格分隔。题目保证没有重复的账号。

输出格式：

首先在一行中输出发出的 PAT 代金券的总面值。然后按总评成绩非升序输出进入名人堂的学生的名次、账号和成绩，其间以 1 个空格分隔。需要注意的是：成绩相同的学生享有并列的排名，排名并列时，按账号的字母序升序输出。

输入样例：
    10 80 5
    cy@zju.edu.cn 78
    cy@pat-edu.com 87
    1001@qq.com 65
    uh-oh@163.com 96
    test@126.com 39
    anyone@qq.com 87
    zoe@mit.edu 80
    jack@ucla.edu 88
    bob@cmu.edu 80
    ken@163.com 70
    
    输出样例：
    360
    1 uh-oh@163.com 96
    2 jack@ucla.edu 88
    3 anyone@qq.com 87
    3 cy@pat-edu.com 87
    5 bob@cmu.edu 80
    5 zoe@mit.edu 80

这道题对于使用 STL 的选手来说就是福利啊。  
**可以用一个结构体来保存每一个学生的信息（邮箱、成绩），之后定义一个该结构体的数组，然后根据题目 的意思对这个结构体数组进行自定义排序。最后就是输出了**

**对于输出需要注意的是并列的学生是会占用一个排名名额的，比如上面测试样例中并列第 3 的后面那个学生把排名为 4 的位置占用了，于是就没有第 4 名了。但是对于最后一名（第 `k` 名是可以有多个学生并列的）。**

代码：

#include <string>
    #include <vector>
    #include <algorithm>
    #include <iostream>
    using namespace std;
    
    // 保存学生信息的结构体：邮箱、分数 
    struct Peo {
        string email;
        int grade;
    };
    const int MAXN = 1e4+10;
    Peo peo[MAXN];
    
    // 自定义数组的排序规则：先按成绩排序，若成绩相同，按邮箱升序
    bool com(Peo p1, Peo p2) {
        if (p1.grade == p2.grade) {
            return p1.email < p2.email;
        }
        return p1.grade > p2.grade;
    } 
    
    int main() {
        int n, g, k, money = 0;
        cin >> n >> g >> k;
        string email;
        int grade;  
        for (int i = 0; i < n; i++) {
            cin >> email >> grade;
            peo[i].email = email;
            peo[i].grade = grade;
            // 统计出发出了多少代金券
            if (grade >= 60 && grade < g) {
                money += 20;
            } else if (grade >= g) {
                money += 50;
            }
        }
        sort(peo, peo + n, com);
    
        cout << money << endl;
        int lastGrade = -1; // 储存上一个学生的成绩
        int currentLevel = 0; // 储存当前学生的排名
        for (int i = 0; i < k; i++) {
            // 如果当前学生的成绩不等于上一个学生的成绩，
            // 证明当前学生的排名在上一个学生的后一名
            if (lastGrade != peo[i].grade) {
                currentLevel = i + 1;
            }
            cout << currentLevel << " " << 
                    peo[i].email << " " << peo[i].grade << endl;
            lastGrade = peo[i].grade;
        }
        // 输出最后所有并列第 k 名的学生信息
        int i = k;
        while (peo[i].grade == lastGrade) {
            cout << currentLevel << " " << 
                    peo[i].email << " " << peo[i].grade << endl;
            i++;
        }
    
        return 0;
    }

好了，今天就只 AC 了这些题，后面的题没有全部 AC，还是等做出来了再补充吧。

[http_www.icourse163.org]: http://www.icourse163.org/