机试day3
排序
描述
对输入的n个数进行排序并输出。
输入描述：
输入的第一行包括一个整数n(1<=n<=100)。 接下来的一行包括n个整数。
输出描述：
可能有多组测试数据，对于每组数据，将排序后的n个整数输出，每个数后面都有一个空格。 每组测试数据的结果占一行。
输入：
4
1 4 3 2
输出：
1 2 3 4 思路：直接引用algorithm库中的sort函数排序即可，后续学习数据机构中的排序算法
#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]);
}
}
}成绩排序
描述
用一维数组存储学号和成绩，然后，按成绩排序输出。
输入描述：
输入第一行包括一个整数N(1<=N<=100)，代表学生的个数。 接下来的N行每行包括两个整数p和q，分别代表每个学生的学号和成绩。
输出描述：
按照学生的成绩从小到大进行排序，并将排序后的学生信息打印出来。 如果学生的成绩相同，则按照学号的大小进行从小到大排序。
思路：使用sort的自定义比较，返回结果为true则x在前，y在后；同时为了更好表示学生这个结构体，使用了struct来预定义
#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);
}
}
}成绩排序
描述
查找和排序
题目：输入任意（用户，成绩）序列，可以获得成绩从高到低或从低到高的排列,相同成绩
都按先录入排列在前的规则处理。
示例：
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
#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;
}
}
}特殊排序
描述
输入一系列整数，将其中最大的数挑出(如果有多个，则挑出一个即可)，并将剩下的数进行排序，如果无剩余的数，则输出-1。
输入描述：
输入第一行包括1个整数N，1<=N<=1000，代表输入数据的个数。 接下来的一行有N个整数。
输出描述：
可能有多组测试数据，对于每组数据， 第一行输出一个整数，代表N个整数中的最大值，并将此值从数组中去除，将剩下的数进行排序。 第二行将排序的结果输出。
思路：没啥特殊的，无非是排好后的数组，最后一个输出在第一行，剩下的输出在下一行；如果没有剩下的输出-1即可
#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)
描述
输入10个整数，彼此以空格分隔。重新排序以后输出(也按空格分隔)，要求: 1.先输出其中的奇数,并按从大到小排列； 2.然后输出其中的偶数,并按从小到大排列。
输入描述：
任意排序的10个整数（0～100），彼此以空格分隔。
输出描述：
可能有多组测试数据，对于每组数据，按照要求排序后输出，由空格分隔。 1. 测试数据可能有很多组，请使用while(cin>>a[0]>>a[1]>>...>>a[9])类似的做法来实现; 2. 输入数据随机，有可能相等。
法1：分别接收奇数和偶数
思路：分别定义了偶数和奇数数组接收，分别排序，看起来有些麻烦
#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函数
该函数如下，短短的一行，十分震撼！
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 | , |
所以计算先后顺序是：
- 比较x、y大小，得到0或1
- 按位异或，将0或1和x异或，如果x是偶数，0和x异或得到偶数，1和x异或得到奇数；如果x是奇数，0和x异或得到奇数，1和x异或得到偶数
- 按位与，偶数和1与得到0，奇数和1与得到1
假设都是奇数，x<y，则为1，1和x异或得到偶数，偶数和1与得到0，因此同为奇数小的放后面，即降序
假设都是偶数，x<y，则为1，1和x异或得到奇数，奇数和1与得到1，因此同为偶数小的放前面，即升序
来看下ChatGPT咋解释[doge]，可以看到直接问这句代码啥意思，他不清楚
但是你把整个比较函数给出来，并说明这是c++的sort函数中的第三个参数，他答案完全正确，就是分析比较浅层！
ChatGPT 赞！
法3：比法2简单点，不要这么复杂的三目了
思路：四种情况都去做个判断！
#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]);
}
}
}小白鼠排队
描述
N只小白鼠(1 <= N <= 100)，每只鼠头上戴着一顶有颜色的帽子。现在称出每只白鼠的重量，要求按照白鼠重量从大到小的顺序输出它们头上帽子的颜色。帽子的颜色用“red”，“blue”等字符串来表示。不同的小白鼠可以戴相同颜色的帽子。白鼠的重量用整数表示。
输入描述：
多案例输入，每个案例的输入第一行为一个整数N，表示小白鼠的数目。 下面有N行，每行是一只白鼠的信息。第一个为不大于100的正整数，表示白鼠的重量，；第二个为字符串，表示白鼠的帽子颜色，字符串长度不超过10个字符。 注意：白鼠的重量各不相同。
输出描述：
每个案例按照白鼠的重量从大到小的顺序输出白鼠的帽子颜色。
思路：前面做过了此题便简单至极
#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:】
关键点：
- 注意比例可能有小数，因此不可以使用int型了（最开始测试案例对了，但提交却一堆通不过）
- 先遍历需要找最好排名及排名方式的国家，再遍历四种排序方式；具体而言就是把四种值存储到二维字典中，一行行比较，选取最小排名及其排名方式
- 注意！！！可能会有金牌数或总奖牌数为0的情况，甚至有人口为0！？这咋除，我当时花了好长时间排查这个除以0的bug，甚至动用了math库里判断inf或nan的函数，但始终有那么一组案例中的一个不对。事实证明不是根据人口数为0设置比例为0，而是前两个奖牌数为0时设置比例为0，原因搞不懂，感觉题目有些bug
#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：排序算法思路
下一次看
