Loading... # 机试day3 ## 排序 [排序_牛客题霸_牛客网 (nowcoder.com)](https://www.nowcoder.com/practice/508f66c6c93d4191ab25151066cb50ef?tpId=40&tqId=21542&tPage=1&rp=1&ru=/ta/kaoyan&qru=/ta/kaoyan/question-ranking) **描述** 对输入的n个数进行排序并输出。 **输入描述**: 输入的第一行包括一个整数n(1<=n<=100)。 接下来的一行包括n个整数。 **输出描述**: 可能有多组测试数据,对于每组数据,将排序后的n个整数输出,每个数后面都有一个空格。 每组测试数据的结果占一行。 ~~~ 输入: 4 1 4 3 2 输出: 1 2 3 4 ~~~ 思路:直接引用algorithm库中的sort函数排序即可,后续学习数据机构中的排序算法 ~~~c++ #include <iostream> #include <algorithm> using namespace std; int main() { int n; while (scanf("%d", &n)!=EOF) { int arr[n]; for (int i = 0; i < n; i++) { scanf("%d", arr + i); } sort(arr, arr + n); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } } } ~~~ ## 成绩排序 [成绩排序_牛客题霸_牛客网 (nowcoder.com)](https://www.nowcoder.com/practice/3f27a0a5a59643a8abf0140b9a8cf1f7?tpId=40&tqId=21340&tPage=1&rp=1&ru=/ta/kaoyan&qru=/ta/kaoyan/question-ranking) **描述** 用一维数组存储学号和成绩,然后,按成绩排序输出。 **输入描述**: 输入第一行包括一个整数N(1<=N<=100),代表学生的个数。 接下来的N行每行包括两个整数p和q,分别代表每个学生的学号和成绩。 **输出描述**: 按照学生的成绩从小到大进行排序,并将排序后的学生信息打印出来。 如果学生的成绩相同,则按照学号的大小进行从小到大排序。 思路:使用sort的自定义比较,返回结果为true则x在前,y在后;同时为了更好表示学生这个结构体,使用了struct来预定义 ~~~c++ #include <iostream> #include <algorithm> using namespace std; struct Student{ int number, score; }; bool compare(Student x, Student y){ if (x.score == y.score) { return x.number < y.number; } else { return x.score < y.score; } } int main() { int n; while (scanf("%d", &n)!=EOF) { Student s[n]; for (int i = 0; i < n; i++) { scanf("%d %d", &s[i].number, &s[i].score); } sort(s, s + n, compare); for (int i = 0; i < n; i++) { printf("%d %d\n", s[i].number, s[i].score); } } } ~~~ ## 成绩排序 [成绩排序_牛客题霸_牛客网 (nowcoder.com)](https://www.nowcoder.com/practice/0383714a1bb749499050d2e0610418b1?tpId=40&tqId=21333&tPage=1&rp=1&ru=/ta/kaoyan&qru=/ta/kaoyan/question-ranking) **描述** 查找和排序 题目:输入任意(用户,成绩)序列,可以获得成绩从高到低或从低到高的排列,相同成绩 都按先录入排列在前的规则处理。 示例: jack 70 peter 96 Tom 70 smith 67 从高到低 成绩 peter 96 jack 70 Tom 70 smith 67 从低到高 smith 67 jack 70 Tom 70 peter 96 **输入描述**: 注意一个case里面有多组样例,请用循环处理输入 输入多行,先输入要排序的人的个数,然后输入排序方法0(降序)或者1(升序)再分别输入他们的名字和成绩,以一个空格隔开。 **输出描述**: 按照指定方式输出名字和成绩,名字和成绩之间以一个空格隔开 思路:本题在前两题的基础上增加了选择是否升序或降序,因此分别写俩函数即可,另外增加了string类型,输入输出最好用c++的方式,即cin、cout ~~~c++ #include <iostream> #include <algorithm> using namespace std; struct Student{ string name; int score, order; }; bool CompareDescending(Student x, Student y){ if (x.score == y.score) { return x.order < y.order; } else { return x.score > y.score; } } bool CompareAscending(Student x, Student y){ if (x.score == y.score) { return x.order < y.order; } else { return x.score < y.score; } } int main() { int n, compare; while(scanf("%d", &n)!=EOF) { Student s[n]; scanf("%d", &compare); for (int i = 0; i < n; i++) { cin >> s[i].name >> s[i].score; s[i].order = i; } if (compare) { sort(s, s + n, CompareAscending); } else { sort(s, s + n, CompareDescending); } for (int i = 0; i < n; i++) { cout << s[i].name << " " << s[i].score << endl; } } } ~~~ ## 特殊排序 [特殊排序_牛客题霸_牛客网 (nowcoder.com)](https://www.nowcoder.com/practice/57f0f528bff149be9580af66f6292430?tpId=40&tqId=21543&tPage=1&rp=1&ru=/ta/kaoyan&qru=/ta/kaoyan/question-ranking) **描述** 输入一系列整数,将其中最大的数挑出(如果有多个,则挑出一个即可),并将剩下的数进行排序,如果无剩余的数,则输出-1。 **输入描述**: 输入第一行包括1个整数N,1<=N<=1000,代表输入数据的个数。 接下来的一行有N个整数。 **输出描述**: 可能有多组测试数据,对于每组数据, 第一行输出一个整数,代表N个整数中的最大值,并将此值从数组中去除,将剩下的数进行排序。 第二行将排序的结果输出。 思路:没啥特殊的,无非是排好后的数组,最后一个输出在第一行,剩下的输出在下一行;如果没有剩下的输出-1即可 ~~~c++ #include <iostream> #include <algorithm> using namespace std; int main() { int n; while (scanf("%d", &n) != EOF) { int arr[n]; for (int i = 0; i < n; i++) { scanf("%d", arr + i); } sort(arr, arr + n); printf("%d\n", arr[n-1]); if (n - 1) { for (int i = 0; i < n-1; i++) { printf("%d ", arr[i]); } } else { printf("-1"); } } } ~~~ ## 整数奇偶排序 [整数奇偶排序_牛客题霸_牛客网 (nowcoder.com)](https://www.nowcoder.com/practice/bbbbf26601b6402c9abfa88de5833163?tpId=40&tqId=21398&tPage=1&rp=1&ru=/ta/kaoyan&qru=/ta/kaoyan/question-ranking) **描述** 输入10个整数,彼此以空格分隔。重新排序以后输出(也按空格分隔),要求: 1.先输出其中的奇数,并按从大到小排列; 2.然后输出其中的偶数,并按从小到大排列。 **输入描述**: 任意排序的10个整数(0~100),彼此以空格分隔。 **输出描述**: 可能有多组测试数据,对于每组数据,按照要求排序后输出,由空格分隔。 1. 测试数据可能有很多组,请使用while(cin>>a[0]>>a[1]>>...>>a[9])类似的做法来实现; 2. 输入数据随机,有可能相等。 ### 法1:分别接收奇数和偶数 思路:分别定义了偶数和奇数数组接收,分别排序,看起来有些麻烦 ~~~c++ #include <cstdio> #include <iostream> #include <algorithm> using namespace std; bool CompareDescending(int x, int y){ return x > y; } int main() { int odd[10], even[10], a[10]; while (cin>>a[0]>>a[1]>>a[2]>>a[3]>>a[4]>>a[5]>>a[6]>>a[7]>>a[8]>>a[9]) { int odd_n = 0, even_n = 0; for (int i = 0; i < 10; i++) { if (a[i] % 2) { odd[odd_n++] = a[i]; } else { even[even_n++] = a[i]; } } sort(odd, odd + odd_n, CompareDescending); sort(even, even + even_n); for (int i = 0; i < odd_n; i++) { printf("%d ", odd[i]); } for (int i = 0; i < even_n; i++) { printf("%d ", even[i]); } } } ~~~ ### 法2:自定义一个全新且十分巧妙的sort函数 该函数如下,短短的一行,十分震撼! ~~~c++ bool compare(int x, int y){ return x % 2 != y % 2 ? x % 2 > y % 2 : x < y ^ x & 1; } ~~~ **原理解析下**:这是一个三目运算,最开始的条件判断的是是否同奇数或同偶数,如果不是奇数的排前面,偶数的排后面。接着如果都是奇数或偶数,使用y ^ x \& 1来判断大小,这句话涉及了**运算符的优先级**! | 优先级 | 运算符 | | :------: | :---------------------------------------------------------------------------------: | | 1 | \[] \() \. -\> | | 2 | \-(负号运算符) \~(取反符号) ++ -- \*(取值运算符) &(取地址运算符) !(逻辑非) sizeof | | 3 | / *(除号) % | | 4 | + -(减号) | | 5 | << >> | | 6 | \> \>= < \<\= | | 7 | \=\= !\= | | 8 | &(按位与) | | 9 | ^(按位异或) | | 10 | \|(按位或) | | 11 | && | | 12 | \|\| | | 13 | ?:(条件运算符) | | 14 | = += -= /= *= %= <<= >>= &=\|= ^=(各种先计算后赋值) | | 15 | , | 所以计算先后顺序是: 1. 比较x、y大小,得到0或1 2. 按位异或,将0或1和x异或,如果x是偶数,0和x异或得到偶数,1和x异或得到奇数;如果x是奇数,0和x异或得到奇数,1和x异或得到偶数 3. 按位与,偶数和1与得到0,奇数和1与得到1 假设都是奇数,x<y,则为1,1和x异或得到偶数,偶数和1与得到0,因此同为奇数小的放后面,即降序 假设都是偶数,x<y,则为1,1和x异或得到奇数,奇数和1与得到1,因此同为偶数小的放前面,即升序 来看下ChatGPT咋解释[doge],可以看到直接问这句代码啥意思,他不清楚 ![image-20230526203548931.png](http://xherlock.top/usr/uploads/2023/05/1808712857.png) 但是你把整个比较函数给出来,并说明这是c++的sort函数中的第三个参数,他答案完全正确,就是分析比较浅层! ![image-20230526204022156.png](http://xherlock.top/usr/uploads/2023/05/3769989627.png) ChatGPT 赞! ### 法3:比法2简单点,不要这么复杂的三目了 思路:四种情况都去做个判断! ~~~c++ #include <cstdio> #include <iostream> #include <algorithm> using namespace std; bool compare(int x, int y){ if (x % 2 == 1 && y % 2 == 1) { return x > y; } else if (x % 2 == 0 && y % 2 == 0) { return x < y; } else if (x % 2 == 1 && y % 2 == 0) { return true; // 奇数放前面 } else { return false; // 偶数放后面 } } int main() { int a[10]; while (cin>>a[0]>>a[1]>>a[2]>>a[3]>>a[4]>>a[5]>>a[6]>>a[7]>>a[8]>>a[9]) { sort(a, a + 10, compare); for (int i = 0; i < 10; i++) { printf("%d ", a[i]); } } } ~~~ ## 小白鼠排队 [小白鼠排队_牛客题霸_牛客网 (nowcoder.com)](https://www.nowcoder.com/practice/27fbaa6c7b2e419bbf4de8ba60cf372b?tpId=61&tqId=29509&tPage=1&ru=/kaoyan/retest/1002&qru=/ta/pku-kaoyan/question-ranking) **描述** N只小白鼠(1 <= N <= 100),每只鼠头上戴着一顶有颜色的帽子。现在称出每只白鼠的重量,要求按照白鼠重量从大到小的顺序输出它们头上帽子的颜色。帽子的颜色用“red”,“blue”等字符串来表示。不同的小白鼠可以戴相同颜色的帽子。白鼠的重量用整数表示。 **输入描述**: 多案例输入,每个案例的输入第一行为一个整数N,表示小白鼠的数目。 下面有N行,每行是一只白鼠的信息。第一个为不大于100的正整数,表示白鼠的重量,;第二个为字符串,表示白鼠的帽子颜色,字符串长度不超过10个字符。 注意:白鼠的重量各不相同。 **输出描述**: 每个案例按照白鼠的重量从大到小的顺序输出白鼠的帽子颜色。 思路:前面做过了此题便简单至极 ~~~c++ #include <iostream> #include <algorithm> using namespace std; struct Mouse { int weight; string color; }; bool compare(Mouse x, Mouse y) { return x.weight > y.weight; } int main() { int N; while (scanf("%d", &N) != EOF) { Mouse m[N]; for (int i = 0; i < N; i++) { cin >> m[i].weight >> m[i].color; } sort(m, m + N, compare); for (int i = 0; i < N; i++) { cout << m[i].color << endl; } } } ~~~ ## 奥运排序问题 **描述** 按要求,给国家进行排名。 **输入描述**: 有多组数据。 第一行给出国家数N,要求排名的国家数M,国家号从0到N-1。 第二行开始的N行给定国家或地区的奥运金牌数,奖牌数,人口数(百万)。 接下来一行给出M个国家号。 **输出描述**: 排序有4种方式: 金牌总数 奖牌总数 金牌人口比例 奖牌人口比例 对每个国家给出最佳排名排名方式 和 最终排名 格式为: 排名:排名方式 如果有相同的最终排名,则输出排名方式最小的那种排名,对于排名方式,金牌总数 < 奖牌总数 < 金牌人口比例 < 奖牌人口比例 如果有并列排名的情况,即如果出现金牌总数为 100,90,90,80.则排名为1,2,2,4. 每组数据后加一个空行。 ~~~ 输入: 4 4 4 8 1 6 6 2 4 8 2 2 12 4 0 1 2 3 4 2 8 10 1 8 11 2 8 12 3 8 13 4 0 3 输出: 1:3 1:1 2:1 1:2 1:1 1:1 ~~~ ### 法1:暴力遍历,没用到排序 思路:最开始想用排序来着,但没思路怎么设计结构比较多种排序方式;因此瞅了眼评论区,看到一个思路是遍历所有国家,排名比自己好的给自己的排名+1;思路很好,具体案例一堆bug【如下,提交了20次,最后两次才对:cry:】 ![image-20230526231135952.png](http://xherlock.top/usr/uploads/2023/05/1370830703.png) 关键点: 1. 注意比例可能有小数,因此不可以使用int型了(最开始测试案例对了,但提交却一堆通不过) 2. 先遍历需要找最好排名及排名方式的国家,再遍历四种排序方式;具体而言就是把四种值存储到二维字典中,一行行比较,选取最小排名及其排名方式 3. 注意!!!可能会有金牌数或总奖牌数为0的情况,甚至有人口为0!?这咋除,我当时花了好长时间排查这个除以0的bug,甚至动用了math库里判断inf或nan的函数,但始终有那么一组案例中的一个不对。事实证明不是根据人口数为0设置比例为0,而是前两个奖牌数为0时设置比例为0,原因搞不懂,感觉题目有些bug ~~~c++ #include <iostream> #include <algorithm> using namespace std; int main() { int N, M; while (scanf("%d%d", &N, &M) != EOF) { float c[N][4]; for (int i = 0; i < N; i++) { scanf("%f%f%f", &c[i][0], &c[i][1], &c[i][2]); c[i][3] = c[i][1] ? c[i][1] * 1.0 / c[i][2] : 0; c[i][2] = c[i][0] ? c[i][0] * 1.0 / c[i][2] : 0; // printf("%f %f %f %f\n", c[i][0], c[i][1], c[i][2], c[i][3]); } int country_order[M]; for (int j = 0; j < M; j++) { scanf("%d", &country_order[j]); } for (int k = 0; k < M; k++) { int best_rank = N, best_sort = 1; for (int j = 0; j < 4; j++) { int rank = 1; for (int i = 0; i < N; i++) { if (c[i][j] > c[country_order[k]][j]) { rank += 1; } } if (rank < best_rank) { best_rank = rank; best_sort = j + 1; } } printf("%d:%d\n", best_rank, best_sort); } printf("\n"); } } ~~~ ### 法2:排序算法思路 下一次看 最后修改:2023 年 05 月 26 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 0 如果觉得我的文章对你有用,请随意赞赏