专栏首页指点的专栏2018 团队设计天梯赛题解---华山论剑组

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

写在前面

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 的前一个字符串就是 zzyzza 的前一个字符串就是 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/ )学习“数据结构”课程的学生,想要获得一张合格证书,总评成绩必须达到 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,还是等做出来了再补充吧。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 不与版本帝争,16 年后 SciPy 1.0 版终发布

    SciPy 是一个开源的 Python 算法库和数学工具包。SciPy 包含的模块有最优化、线性代数、积分、插值、特殊函数、快速傅里叶变换、信号处理和图像处理、...

    Debian社区
  • React Native APP签名打包release版本APK

    首先React Native开发的APP是无法通过Android Studio进行打包的,因为AS打包的APK,也是和debug版本一样,需要进行依托local...

    做全栈攻城狮
  • 简洁易用可扩展,一个基于深度学习的 CTR 模型包

    在计算广告和推荐系统中,CTR 预估一直是一个核心问题。无论在工业界还是学术界都是一个热点研究问题,近年来也有若干相关的算法竞赛。

    用户1737318
  • 多达 95% 的 HTTPS 链接能被黑客劫持

    HSTS 是一个被当前大多数 Web 浏览器所支持的 Web 安全策略,它可以帮助 Web 管理员保护他们的服务器和用户避免遭到 HTTPS 降级、中间人攻击和...

    Debian社区
  • Debian升级内核开启TCP_BBR 实现网络单边加速

    自从锐速发布以来,这款牛逼的单边加速神器的确为一些线路不太优秀的服务器带来了更优秀的体验。但是呢,过高的价格和不再低端售卖。导致了我们并无法实现一个免费好用的单...

    Debian社区
  • 电脑小白学习软件开发(9)-C#基础数组最大值,最小值及排序

    上次说了枚举字符串以及数组的一部分知识点,其实这些东西枯燥的很。小编在以前学习的时候也是如此。虽然枯燥,但这是做所有项目的基础。今天主要讲解点数组的基础知识,这...

    做全栈攻城狮
  • NeurIPS 2018 | 腾讯AI Lab&amp;北大提出基于随机路径积分的差分估计子非凸优化方法

    作者: Cong Fang, Chris Junchi Li, Zhouchen Lin, Tong Zhang

    机器之心
  • Google 宣布新拥堵控制算法 TCP BBR

    Google 宣布了 新拥堵控制算法 TCP BBR。Google 官方博客称新算法将 google.com 和 YouTube 的全球网络吞吐量平均改进了 4...

    Debian社区
  • 张宏江:人工智能的长远发展需要有人坐冷板凳

    从金山 CEO 退休两年后,除了在源码资本任职投资合伙人,张宏江又在刚刚成立不久的北京智源人工智能研究院担任首届理事长,致力于推动不同行业分享大数据,让从事基础...

    AI科技大本营
  • 巧用OpenSSL完成md2、md4、md5、rmd160、sha、sha1等的验证

    版权声明:本文为耕耘实录原创文章,各大自媒体平台同步更新。欢迎转载,转载请注明出处,谢谢

    耕耘实录

扫码关注云+社区

领取腾讯云代金券