当前位置：首页 > news >正文

洛谷【排序】算法的题单 - 笔记

news 来源：原创 2025/7/14 8:03:37

2024-12-09 - 第 37 篇
洛谷【排序】题单 - 笔记
作者(Author): 郑龙浩 / 仟濹(CSND账号名)

洛谷【排序】题单合集

一、排序算法都有…

1. 简单排序算法

这些算法通常是基础的排序方法，容易理解和实现，但效率较低，适用于数据量较小的情况。

冒泡排序 (Bubble Sort)
时间复杂度：O(n²)
空间复杂度：O(1)
特点：重复地交换相邻的元素，直到整个序列有序。
选择排序 (Selection Sort)
时间复杂度：O(n²)
空间复杂度：O(1)
特点：每次选择最小的元素放到已排序部分的末尾。
插入排序 (Insertion Sort)
时间复杂度：O(n²)
空间复杂度：O(1)
特点：将未排序部分的元素插入到已排序部分的合适位置。

2. 分治排序算法

这些算法通过将大问题分解成小问题来解决，通常效率较高。

归并排序 (Merge Sort)
时间复杂度：O(n log n)
空间复杂度：O(n)
特点：通过递归分解数组并合并已经排序的子数组。
快速排序 (Quick Sort)
时间复杂度：O(n log n)（平均情况），O(n²)（最坏情况）
空间复杂度：O(log n)（递归栈空间）
特点：通过选择一个"基准"元素并将数组分割为小于基准和大于基准的部分，递归地排序。
堆排序 (Heap Sort)
时间复杂度：O(n log n)
空间复杂度：O(1)
特点：通过构建最大堆或最小堆来排序元素。

3. 线性时间排序算法

这些算法的时间复杂度是 O(n)，适用于特定类型的数据。

计数排序 (Counting Sort)
时间复杂度：O(n + k)
空间复杂度：O(k)
特点：通过统计数组中每个元素的出现次数，适用于元素范围较小的情况。
桶排序 (Bucket Sort)
时间复杂度：O(n + k)（最理想情况）
空间复杂度：O(n)
特点：将元素分配到不同的桶中，然后分别排序桶内的元素。
基数排序 (Radix Sort)
时间复杂度：O(nk)
空间复杂度：O(n + k)
特点：按位（从低位到高位）进行排序，适用于整数或字符串排序。

4. 非比较排序算法

这些排序算法通过特定方式排序，不依赖于元素的比较，因此能在某些特定情况下达到线性时间复杂度。

计数排序、桶排序、基数排序 都属于非比较排序，它们利用额外的信息（例如元素的计数、元素分布或位数）来直接排定顺序。

5. 其他排序算法

希尔排序 (Shell Sort)
时间复杂度：O(n log n)（最优情况），O(n²)（最坏情况）
空间复杂度：O(1)
特点：是插入排序的一种改进，采用了分组插入排序，逐步减少间隔来进行排序。
双向冒泡排序 (Cocktail Shaker Sort)
时间复杂度：O(n²)
空间复杂度：O(1)
特点：是冒泡排序的变种，优化了冒泡过程，双向交替进行排序。

总结：排序算法的分类与选择

简单排序（冒泡、选择、插入排序）适用于数据量较小的场景。
分治算法（快速、归并、堆排序）是更高效的排序方法，适用于数据量较大的情况。
线性时间排序（计数、桶、基数排序）适用于特定场景，尤其是在数据范围已知的情况下。

不同的排序算法有不同的应用场景和优缺点，选择排序算法时要考虑输入数据的特点和所需的性能要求。

二、洛谷算法题合集 (基本上都是使用的 sort 函数)

题目顺序由简到难

1. P2676 [USACO07DEC] Bookshelf B

难度【入门】

题目描述

Farmer John 最近为奶牛们的图书馆添置了一个巨大的书架，尽管它是如此的大，但它还是几乎瞬间就被各种各样的书塞满了。现在，只有书架的顶上还留有一点空间。

所有 $\le N \le 20,000)$ 头奶牛都有一个确定的身高 $H_i(1 \le H_i \le 10,000)$ 。设所有奶牛身高的和为S。书架的高度为 $B$ ，并且保证 $\le B \le S < 2,000,000,007$ 。

为了够到比最高的那头奶牛还要高的书架顶，奶牛们不得不像演杂技一般，一头站在另一头的背上，叠成一座“奶牛塔”。当然，这个塔的高度，就是塔中所有奶牛的身高之和。为了往书架顶上放东西，所有奶牛的身高和必须不小于书架的高度。

显然，塔中的奶牛数目越多，整座塔就越不稳定，于是奶牛们希望在能够到书架顶的前提下，让塔中奶牛的数目尽量少。现在，奶牛们找到了你，希望你帮她们计算这个最小的数目。

输入格式

第 $1$ 行: 2 个用空格隔开的整数： $N$ 和 $B$ ；
第 $2\dots N+1$ 行: 第 $i + 1$ 行是 $1$ 个整数： $H_i$ 。

输出格式

第 $1$ 行: 输出 $1$ 个整数，即最少要多少头奶牛叠成塔，才能够到书架顶部

样例 #1

样例输入 #1

样例输出 #1

提示

输入说明:

一共有 $6$ 头奶牛，书架的高度为 $40$ ，奶牛们的身高在 $6\dots19$ 之间。

输出说明:

一种只用 $3$ 头奶牛就达到高度 $40$ 的方法： $18 + 11 + 13$ 。当然还有其他方法，在此不一一列出了。

本题代码:

// P2676-Bookshelf_B
// 使用 sort 函数，快速排序
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
bool cmp( int a, int b ){return a > b;
}
int main( void ){int num, shelf_height; // 奶牛数量，书架高度vector<int> cows_height; // 奶牛高度int sum = 0; // 叠罗汉的奶牛数量cin >> num >> shelf_height;for( int i = 0; i < num; i++ ){int temp;cin >> temp;cows_height.push_back( temp );}sort( cows_height.begin(), cows_height.end(), cmp ); // sort 默认升序，所以可以写一个cmp函数来实现降序for( int i = 0; i < cows_height.size(); i++ ){sum += cows_height[i];if( sum >= shelf_height ){cout << i + 1;break;}}return 0;
}

2.P1152欢乐的跳

难度【入门】

题目描述

一个 $n$ 个元素的整数数组，如果数组两个连续元素之间差的绝对值包括了 $[1, n - 1]$ 之间的所有整数，则称之符合“欢乐的跳”，如数组 ${1,4,2,3\}$ 符合“欢乐的跳”，因为差的绝对值分别为： $3, 2, 1$ 。

给定一个数组，你的任务是判断该数组是否符合“欢乐的跳”。

输入格式

每组测试数据第一行以一个整数 $\le n \le 1000)$ 开始，接下来 $n$ 个空格隔开的在 $10^8,10^8]$ 之间的整数。

输出格式

对于每组测试数据，输出一行若该数组符合“欢乐的跳”则输出 Jolly，否则输出 Not jolly。

样例 #1

样例输入 #1

4 1 4 2 3

样例输出 #1

Jolly

样例 #2

样例输入 #2

5 1 4 2 -1 6

样例输出 #2

Not jolly

提示

$\le n \le 1000$

本题代码:

// 洛谷P1152 欢乐的跳
// 思路：
// 1. 输入数据
// 2. 将相邻两个元素的差值的绝对值存入第二个数组 arr2中
// 3. 将 arr2 差值的绝对值组成的数组 --> 从大到小排序
// 3. 只需比较最大的元素，如果最大的元素 范围在[1, n-1]，而是 “欢乐的跳”, 否则不是“欢乐的跳”
// 3. 条件：数组宽度 1 <= n <= 1000
// 4. 条件：数组元素 -10^8 <= arr[ i ] <= 10^8
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
bool compare( long long a, long long b ){return a > b;
}
int main( void ){vector <long long> arr; // 存储元素vector <long long> arr2;int n; // 数组宽度cin >> n;// 输入数据for( int i = 0; i < n; i++ ){int temp;cin >> temp;arr.push_back( temp );}// 计算相邻两个元素的差值的绝对值for( int i = 0; i < n - 1; i++ ){arr2.push_back( abs( arr[ i ] - arr[ i + 1 ] ) );}// 排序sort( arr2.begin(), arr2.end(), compare );// 比较if( arr2[ 0 ] >= 1 && arr2[ 0 ] <= n - 1 ){cout << "Jolly" << endl;}else{cout << "Not jolly" << endl;}return 0;
}

3.【深基9.例1】选举学生会

难度【普及-】

题目描述

学校正在选举学生会成员，有 $n$ （ $n\le 999$ ）名候选人，每名候选人编号分别从 $1$ 到 $n$ ，现在收集到了 $m$ （ $\le 2000000$ ）张选票，每张选票都写了一个候选人编号。现在想把这些堆积如山的选票按照投票数字从小到大排序。

输入格式

输入 $n$ 和 $m$ 以及 $m$ 个选票上的数字。

输出格式

求出排序后的选票编号。

样例 #1

样例输入 #1

5 10
2 5 2 2 5 2 2 2 1 2

样例输出 #1

1 2 2 2 2 2 2 2 5 5

本题代码:

// 洛谷 P1270 选举学生会
// 思路: 正常排序，没什么特殊的
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main( void ){int num, m; // 人员编号 人数vector<int> arr;cin >> num >> m; // 输入界限// 输入数据for( int i = 0; i < m; i++ ){int temp;cin >> temp;arr.push_back( temp );}// 排序sort( arr.begin(), arr.end() ); // 默认升序排序即可for( int i = 0; i < m; i++ ){cout << arr.at( i ) << " ";}return 0;
}

4.【模板】排序

难度【普及-】

题目描述

将读入的 $N$ 个数从小到大排序后输出。

输入格式

第一行为一个正整数 $N$ 。

第二行包含 $N$ 个空格隔开的正整数 $a_i$ ，为你需要进行排序的数。

输出格式

将给定的 $N$ 个数从小到大输出，数之间空格隔开，行末换行且无空格。

样例 #1

样例输入 #1

5
4 2 4 5 1

样例输出 #1

1 2 4 4 5

提示

对于 $20\%$ 的数据，有 $\leq N \leq 10^3$ ；

对于 $100\%$ 的数据，有 $\leq N \leq 10^5$ ， $\le a_i \le 10^9$ 。

本题代码:

// 洛谷P11177 【模板】排序
// 排序依然是正常排序，需要注意的是细节：【输出格式】行末换行且无空格 --> 这句话意味着需要进行“特判”，行末无空格，而是\n
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main ( void ){int num; // 限制长度vector <int> arr; // 存储数据cin >> num; // 输入数据for( int i = 0; i < num; i++ ){int temp;cin >> temp;arr.push_back( temp );}// 排序sort( arr.begin(), arr.end() ); // 默认升序排序即可for( auto i = arr.begin(); i!= arr.end(); i++ ){cout << *i;if( i!= arr.end() - 1 ){cout << " ";}else{cout << endl;}} // 注意：行末无空格，而是\n ( 最后一个元素后面无空格，而是\n)return 0;
}

5. 【深基9.例4】求第 k 小的数

难度【普及-】

题目描述

输入 $n$ （ $\le n < 5000000$ 且 $n$ 为奇数）个数字 $a_i$ （ $\le a_i < {10}^9$ ），输出这些数字的第 $k$ 小的数。最小的数是第 $0$ 小。

请尽量不要使用 nth_element 来写本题，因为本题的重点在于练习分治算法。

输入格式

输出格式

样例 #1

样例输入 #1

5 1
4 3 2 1 5

样例输出 #1

本题代码:

// 洛谷P1923 第 k 小的数
// 本来的思路是使用 sort 进行排序，然后查找第 k 个元素，但是当数据非常多的时候，超时了
// 然后看了题解以后，发现了一个非常好用的方法，nth_element()方法，然后在CSDN上看了一下如何使用，才用的这个方法
// 注意：在写nth_element()方法的时候，第二个参数无需 k - 1，因为题干中明确指出了【k从0开始】，也就是意味着，k与下标是对齐的
// 注意: 使用cin输入数组的时候，运算会超时，改用scanf就不会超时了
#include <iostream>
#include <algorithm>
using namespace std;
int main ( void ){int arr[ 5000000 ];int n, k;cin >> n >> k;for( int i = 0; i < n; i++ ){scanf( "%d", &arr[ i ]);}nth_element( arr, arr + k, arr + n ); // 使用该方法，查找 第 k 小的数cout << arr[ k ];return 0;
}

6.[NOIP2006 普及组] 明明的随机数

难度【普及-】

题目描述

明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了 $N$ 个 $1$ 到 $1000$ 之间的随机整数 $(N\leq100)$ ，对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。

输入格式

输入有两行，第 $1$ 行为 $1$ 个正整数，表示所生成的随机数的个数 $N$ 。

第 $2$ 行有 $N$ 个用空格隔开的正整数，为所产生的随机数。

输出格式

输出也是两行，第 $1$ 行为 $1$ 个正整数 $M$ ，表示不相同的随机数的个数。

第 $2$ 行为 $M$ 个用空格隔开的正整数，为从小到大排好序的不相同的随机数。

样例 #1

样例输入 #1

10
20 40 32 67 40 20 89 300 400 15

样例输出 #1

8
15 20 32 40 67 89 300 400

提示

NOIP 2006 普及组第一题

本题代码:

// 洛谷P1059 明明的随机数
// 两种思路：
// 1. 先排序，后去重
// 2. 使用桶排序，下标既是数，元素有值，则证明该数被输入了，最后遍历数组，将>=1的元素输出
// 我使用的 桶排序 方法
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main( void ){int n;int sum = 0;int arr[ 1001 ] = {0}; // 桶排序，下标是数，值是出现的次数cin >> n;for( int i = 0; i < n; i ++ ){int temp;cin >> temp;if( arr[ temp ] == 0 ){sum ++;arr[ temp ] ++;}elsecontinue;}cout << sum << endl;// 遍历数组，输出>=1的元素for( int i = 0; i < 1001; i++ ){if( arr[ i ] >= 1 ){cout << i << " ";}}return 0;
}

7.[NOIP2007 普及组] 奖学金

难度【普及-】

题目背景

NOIP2007 普及组 T1

题目描述

某小学最近得到了一笔赞助，打算拿出其中一部分为学习成绩优秀的前 $5$ 名学生发奖学金。期末，每个学生都有 $3$ 门课的成绩：语文、数学、英语。先按总分从高到低排序，如果两个同学总分相同，再按语文成绩从高到低排序，如果两个同学总分和语文成绩都相同，那么规定学号小的同学排在前面，这样，每个学生的排序是唯一确定的。

任务：先根据输入的 $3$ 门课的成绩计算总分，然后按上述规则排序，最后按排名顺序输出前五名名学生的学号和总分。

注意，在前 $5$ 名同学中，每个人的奖学金都不相同，因此，你必须严格按上述规则排序。例如，在某个正确答案中，如果前两行的输出数据（每行输出两个数：学号、总分) 是：

7 279  
5 279

这两行数据的含义是：总分最高的两个同学的学号依次是 $7$ 号、 $5$ 号。这两名同学的总分都是 $279$ (总分等于输入的语文、数学、英语三科成绩之和) ，但学号为 $7$ 的学生语文成绩更高一些。

如果你的前两名的输出数据是：

5 279  
7 279

则按输出错误处理，不能得分。

输入格式

共 $n + 1$ 行。

第 $1$ 行为一个正整数 $\le 300$ ，表示该校参加评选的学生人数。

第 $2$ 到 $n + 1$ 行，每行有 $3$ 个用空格隔开的数字，每个数字都在 $0$ 到 $100$ 之间。第 $j$ 行的 $3$ 个数字依次表示学号为 $j - 1$ 的学生的语文、数学、英语的成绩。每个学生的学号按照输入顺序编号为 $1\sim n$ （恰好是输入数据的行号减 $1$ ）。

保证所给的数据都是正确的，不必检验。

输出格式

共 $5$ 行，每行是两个用空格隔开的正整数，依次表示前 $5$ 名学生的学号和总分。

样例 #1

样例输入 #1

样例输出 #1

样例 #2

样例输入 #2

样例输出 #2

本题代码:

// 洛谷P1093 奖学金
// 思路: 首先这是一道 结构题 + 排序 的题
// 1. 定义一个结构体，存放数据 -->  学号 + 语文成绩 + 数学成绩 + 英语成绩 + 总分
// 2. 编写比较函数 compare --> sort函数需要使用
// 3. 使用sort函数进行排序
// 4. 正常打印
#include <iostream>
#include <algorithm>
using namespace std;
struct student{int id; // 存放学号int chinese; // 存放语文成绩int math; // 存放数学成绩int english; // 存放英语成绩int sum; // 存放总分
};
// 排序规则 --> sort 函数需要使用的【排序函数】
bool compare( student a, student b ){if ( a.sum != b.sum ) // 如果前后两者总成绩 【不相同】 --> 按照总分排序return a.sum > b.sum; else if ( a.chinese!= b.chinese ) // 总成绩 相同 && 语文成绩 【不相同】 --> 按照语文成绩排序return a.chinese > b.chinese;else // 总成绩 相同 && 语文成绩 相同 && 学号 【不相同】 --> 按照学号排序return a.id < b.id;
}
int main( void ){student score[ 305 ]; // 存放学号 + 成绩 + 总成绩int num;cin >> num; // 输入学生人数for( int i = 0; i < num; i++ ){cin >> score[ i ].chinese >> score[ i ].math >> score[ i ].english; // 存放 语 数 英 成绩score[ i ].sum = score[ i ].chinese + score[ i ].math + score[ i ].english; // 计算 总分score[ i ].id = i + 1; // 存放 学号}// 按照规则进行排序sort( score, score + num, compare );// 正常打印for( int i = 0; i < 5; i++ ){cout << score[ i ].id << " " << score[ i ].sum << endl;}return 0;
}

8.宇宙总统

难度【普及-】

题目描述

地球历公元 6036 年，全宇宙准备竞选一个最贤能的人当总统，共有 $n$ 个非凡拔尖的人竞选总统，现在票数已经统计完毕，请你算出谁能够当上总统。

输入格式

第一行为一个整数 $n$ ，代表竞选总统的人数。

接下来有 $n$ 行，分别为第一个候选人到第 $n$ 个候选人的票数。

输出格式

共两行，第一行是一个整数 $m$ ，为当上总统的人的号数。

第二行是当上总统的人的选票。

样例 #1

样例输入 #1

样例输出 #1

4
1022356

提示

票数可能会很大，可能会到 $100$ 位数字。

$\leq n \leq 20$ 。

本题代码:

// 洛谷P1781 宇宙总统
// 该题需要使用 “高精度整数 / 或者直接存储为字符串”，因为最大100位数，普通类型存储不开
// 用结构体存储 “第n人” + “选票数量” + “票数长度”
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
struct ddd{int n; // 第n人char num[ 101 ]; // 选票数量 --> 因为数据太大，所以需要用 字符数组int len; // 票数长度
};
bool cmp( ddd a, ddd b ){if( a.len != b.len )return a.len > b.len; // 按票数长度降序 --> 长度若大，则百分百票数大elsereturn strcmp( a.num, b.num ) > 0; // 按票数降序 --> 票数越多，越在前
}
int main( void ){int num; // 竞选总统人数cin >> num;ddd president[ num ];for( int i = 0; i < num; i++ ){cin >> president[ i ].num; // 输入选票数量president[ i ].n = i + 1; // 第几个人president[ i ].len = strlen( president[ i ].num ); // 计算票数长度}sort( president, president + num, cmp ); // 排序cout << president[ 0 ].n << endl; // 输出最大票数的人的编号cout << president[ 0 ].num << endl; // 输出最大票数的人的票数return 0;
}

9.车厢重组

难度【普及-】

题目描述

在一个旧式的火车站旁边有一座桥，其桥面可以绕河中心的桥墩水平旋转。一个车站的职工发现桥的长度最多能容纳两节车厢，如果将桥旋转 $180$ 度，则可以把相邻两节车厢的位置交换，用这种方法可以重新排列车厢的顺序。于是他就负责用这座桥将进站的车厢按车厢号从小到大排列。他退休后，火车站决定将这一工作自动化，其中一项重要的工作是编一个程序，输入初始的车厢顺序，计算最少用多少步就能将车厢排序。

输入格式

共两行。

第一行是车厢总数 $\le 10000)$ 。

第二行是 $N$ 个不同的数表示初始的车厢顺序。
（注：实际上数据中并不都在同一行，有可能分行输入）

输出格式

一个整数，最少的旋转次数。

样例 #1

样例输入 #1

4
4 3 2 1

样例输出 #1

本题代码:

// 洛谷P1116 车厢重组 // 一定要记住：即使只计算【步数】，依然要进行中间的【交换】，刚开始做我就犯了这个错，后来才发现！！！！// 该题 使用冒泡的算法，而题目中并未指出要排序，我们不可以省去排序的步骤！！直接打印出题目中想要的 “步数”
// 注:千万不要因为只计算【步骤】，省去【交换】的步骤，这样做出来的答案是错误的，因为既然没有进行交换，那么大数一直没有放到最后边，导致数组中的
// 数据没次循环都是一样的，每次循环大数的位置不是在最后边，所以我们需要进行交换，才能得到正确的答案！！！// 思路：依次循环，每次循环将最大的数字，冒泡到 最后面
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int main( void ){int num; // 车厢数量cin >> num;int ans = 0; // 存储结果 --> 步数vector <int> arr ( num ); // 存储车厢for( int i = 0; i < num; i++ ) // 输入cin >> arr[ i ];for( int i = 0; i < num - 1; i ++ ){ //表示次数，次数为 num - 1 次，因为最后一个数，不需要再循环for( int j = 0; j < num - 1 - i; j ++ ){ // 每次循环，将最大的数，冒泡到最后面，排到 i 位置 ，所以是 1 到 iif( arr[ j ] > arr[ j + 1 ] ){ // 因为是从小到大排，所以如果【当前位置】> 【下一个位置】，则交换位置，并且步数 + 1swap( arr[ j ], arr[ j + 1 ] ); // 交换两数ans ++;}}}cout << ans << endl;return 0;
}

10. [NOIP2009 普及组] 分数线划定

难度【普及-】

题目描述

世博会志愿者的选拔工作正在 A 市如火如荼的进行。为了选拔最合适的人才，A 市对所有报名的选手进行了笔试，笔试分数达到面试分数线的选手方可进入面试。面试分数线根据计划录取人数的 $150\%$ 划定，即如果计划录取 $m$ 名志愿者，则面试分数线为排名第 $\times 150\%$ （向下取整）名的选手的分数，而最终进入面试的选手为笔试成绩不低于面试分数线的所有选手。

现在就请你编写程序划定面试分数线，并输出所有进入面试的选手的报名号和笔试成绩。

输入格式

第一行，两个整数 $\leq n \leq 5000,3 \leq m \leq n)$ ，中间用一个空格隔开，其中 $n$ 表示报名参加笔试的选手总数， $m$ 表示计划录取的志愿者人数。输入数据保证 $\times 150\%$ 向下取整后小于等于 $n$ 。

第二行到第 $n + 1$ 行，每行包括两个整数，中间用一个空格隔开，分别是选手的报名号 $\leq k \leq 9999)$ 和该选手的笔试成绩 $\leq s \leq 100)$ 。数据保证选手的报名号各不相同。

输出格式

第一行，有 $2$ 个整数，用一个空格隔开，第一个整数表示面试分数线；第二个整数为进入面试的选手的实际人数。

从第二行开始，每行包含 $2$ 个整数，中间用一个空格隔开，分别表示进入面试的选手的报名号和笔试成绩，按照笔试成绩从高到低输出，如果成绩相同，则按报名号由小到大的顺序输出。

样例 #1

样例输入 #1

样例输出 #1

提示

【样例说明】

$\times 150\% = 3 \times150\% = 4.5$ ，向下取整后为 $4$ 。保证 $4$ 个人进入面试的分数线为 $88$ ，但因为 $88$ 有重分，所以所有成绩大于等于 $88$ 的选手都可以进入面试，故最终有 $5$ 个人进入面试。

NOIP 2009 普及组第二题

本题代码:

// 洛谷P1068 分数线划定
// 题目有点长，读了一阵子才读明白题意
// 总而言之，就是有一堆人，然后输入n(参赛人数),m(录取人数) 其中：( m * 150% ) <= n 如果 ( m * 150% )为小数，则向下取整 4.5 取 4
// 注意：如果最后的【分数线】是重分，则要将最后一个重分的人也输出，并且输出人数也要 + 1
// 思路：
// 1. 输入 n 和 m
// 2. 输入 n 个分数，存储到数组中
// 3. 对数组进行排序，从大到小
// 4. 计算出 m * 1.5 向下取整的数 new_m，并且判断: 如果arr[ new_m ] 为 重分，则要将【所有重分的人的分数都打印出来，且 new_m ++】
// 5. 输出分数线，以及分数线的人数
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct ddd{int score; // 存放分数int id; // 存放编号
};
bool cmp( ddd a, ddd b ){if( a.score == b.score ) // 如果分数相等，则按照编号从小到大排序return a.id < b.id;return a.score > b.score;
}
int main( void ){int n, m, new_m; // 参赛人数，录取人数, m * 1.5 向下取整cin >> n >> m;ddd arr[ 5001 ]; // 存放分数, 编号 --> 注意：定义数组的时候，千万不要将 5001 写成 变量n，否则，答案会出错for( int i = 0; i < n; i ++ ){ // 输入分数scanf( "%d%d", &arr[ i ].id, &arr[ i ].score );}// 注意: 先排序，后计算 new_m 的大小sort( arr, arr + n, cmp ); // 排序 --> 从大到小 --> 所有人都要排序，因为有重分的情况会出现，这种情况也要排序，并且记入 new_m 中new_m = m * 1.5; // 分数线 --> 如果是小数，则向下取整 --> 实际上就是【数据截断】// 处理【重分】的情况 --> whilewhile( arr[ new_m - 1 ].score == arr[ new_m ].score && new_m < n ){ // 每次循环，如果 分数相同，则 new_m ++ && 保证不越界(new_m < n)new_m ++;}printf( "%d %d\n", arr[ new_m - 1 ], new_m); // 输出分数线，以及分数线的人数for( int i = 0; i < new_m; i ++ ){ // 输出分数线的人的编号printf( "%d %d\n", arr[ i ].id, arr[ i ].score ); }return 0;
}

11.攀爬者

难度【普及-】

题目背景

HKE 考完 GDOI 之后跟他的神犇小伙伴们一起去爬山。

题目描述

他在地形图上标记了 $N$ 个点，每个点 $P_i$ 都有一个坐标 $x_i,y_i,z_i)$ 。所有点对中，高度值 $z$ 不会相等。HKE 准备从最低的点爬到最高的点，他的攀爬满足以下条件：

(1) 经过他标记的每一个点；

(2) 从第二个点开始，他经过的每一个点高度 $z$ 都比上一个点高；

(3) HKE 会飞，他从一个点 $P_i$ 爬到 $P_j$ 的距离为两个点的欧几里得距离。即， $\sqrt{(X_i-X_j)^2+(Y_i-Y_j)^2+(Z_i-Z_j)^2}$

现在，HKE 希望你能求出他攀爬的总距离。

输入格式

第一行，一个整数 $N$ 表示地图上的点数。

接下来 $N$ 行，三个整数 $x_i,y_i,z_i$ 表示第 $i$ 个点的坐标。

输出格式

一个实数，表示 HKE 需要攀爬的总距离（保留三位小数）

样例 #1

样例输入 #1

样例输出 #1

6.928

提示

对于100%的数据， $1\leq N\leq 50000$ ，答案的范围在 double 范围内。

本题代码:

// 洛谷P5143 攀爬者
// 本题方法：1. 使用 ”结构体”数组存储“坐标” 2.  按照“高度”对结构体进行排序  3. 遍历数据，按照数学公式计算距离并且累加距离#include <iostream>
#include <algorithm>
#include <cmath>using namespace std;
struct ddd{int x, y, z; // 存放坐标
};
// 比较函数 - 排序规则：按照高度 从小到大 排序
bool cmp( ddd a, ddd b ){return b.z > a.z; // 按照高度 从小到大 排序
}
int main( void ){ddd point[ 50000 ]; // 存放坐标int n; // 存放坐标的个数cin >> n; // 输入坐标的个数// 输入坐标for( int i = 0; i < n; i ++ ){cin >> point[ i ].x >> point[ i ].y >> point[ i ].z;}sort( point, point + n, cmp ); // 按照高度进行由小到大排序double sum = 0; // 存放总距离// 遍历数据，按照数学公式计算距离并且累加距离for( int i = 0; i < n - 1; i ++ ){ // 为什么是 n - 1 呢？因为 我循环中所写的是： 当前位置 与 后一个位置，// 所以我只需要循环到 point[ n - 2 ] 即可，因为最后一个循环计算的是 point[ n - 1 ] 与 point[ n - 2 ] 的距离int new_x = point[ i ].x - point[ i + 1 ].x; // 存储 两个点的 x 坐标的差值int new_y = point[ i ].y - point[ i + 1 ].y; // 存储 两个点的 y 坐标的差值int new_z = point[ i ].z - point[ i + 1 ].z; // 存储 两个点的 z 坐标的差值sum += sqrt( new_x * new_x + new_y * new_y + new_z * new_z ); // 计算距离并累加距离}printf( "%.3lf\n", sum ); // 输出总距离 --> 保留 3 位小数return 0;
}

12.生日

难度【普及-】

题目描述

cjf 君想调查学校 OI 组每个同学的生日，并按照年龄从大到小的顺序排序。但 cjf 君最近作业很多，没有时间，所以请你帮她排序。

输入格式

输入共有 $n + 1$ 行，

第 $1$ 行为 OI 组总人数 $n$ ；

第 $2$ 行至第 $n + 1$ 行分别是每人的姓名 $s$ 、出生年 $y$ 、月 $m$ 、日 $d$ 。

输出格式

输出共有 $n$ 行，

即 $n$ 个生日从大到小同学的姓名。（如果有两个同学生日相同，输入靠后的同学先输出）

样例 #1

样例输入 #1

3
Yangchu 1992 4 23
Qiujingya 1993 10 13
Luowen 1991 8 1

样例输出 #1

Luowen
Yangchu
Qiujingya

提示

数据保证， $1 < n < 100$ ， $1\leq |s|<20$ 。保证年月日实际存在，且年份 $\in [1960,2020]$ 。

本题代码:

// 洛谷P1104 生日
// 思路：
// 1. 使用 结构体数组 存储人员信息
// 2. 按照 年龄 进行 排序 --> 使用sort函数，比较函数规则：先按照年，再按照月，再按照日，如果都相等，后输入的在前
// 注意：输入靠后的在前，刚开始看错了，看成了先输入的靠前，导致错了
// 3. 输出 结构体数组 中 第 k 个 元素的 姓名
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;// 定义结构体 --> 存储 姓名 年月日 输入顺序
struct ddd{string name;int year, month, day;int num; // 输入顺序 -> 为了方便排序：若年龄相同，则 先输入的 排在 前面
};
// 比较函数 --> 按照年龄进行排序的规则
bool cmp( ddd a, ddd b ){if( a.year != b.year )return a.year < b.year; // 年 小的在前 即 年龄大的在前else if( a.month != b.month )return a.month < b.month; // 月 小的在前 即 年龄大的在前else if( a.day != b.day )return a.day < b.day; // 日 小的在前，即 年龄大的在前elsereturn a.num > b.num; // 输入顺序 小的在前 即 如果年龄完全相等，输入靠后的在前// 一定要注意: 输入靠后的在前，不是输入靠前的在前
}
int main( void ){int n; // 总人数ddd peo[ 100 ]; // 存储人员信息cin >> n; // 输入总人数// 输入人员信息for( int i = 0; i < n; i ++ ){cin >> peo[ i ].name >> peo[ i ].year >> peo[ i ].month >> peo[ i ].day;peo[ i ].num = i + 1; // 记录输入顺序}sort( peo, peo + n, cmp ); // 按照年龄进行排序for( int i = 0; i < n; i ++ ){cout << peo[ i ].name << endl;}cout << endl;return 0;
}

13.[NOIP1998 提高组] 拼数

难度【普及/提高-】

题目描述

设有 $n$ 个正整数 $a_1 \dots a_n$ ，将它们联接成一排，相邻数字首尾相接，组成一个最大的整数。

输入格式

第一行有一个整数，表示数字个数 $n$ 。

第二行有 $n$ 个整数，表示给出的 $n$ 个整数 $a_i$ 。

输出格式

一个正整数，表示最大的整数

样例 #1

样例输入 #1

3
13 312 343

样例输出 #1

34331213

样例 #2

样例输入 #2

4
7 13 4 246

样例输出 #2

提示

对于全部的测试点，保证 $\leq n \leq 20$ ， $\leq a_i \leq 10^9$ 。

NOIP1998 提高组第二题

本题代码:

// 洛谷P1012 拼数
// 思路：
// 本题的排序不是正常的排序，不是比较数值大小 --> 因为是要求出数字拼一起的最大值，所以排序应该是 两数不同顺序相加 哪个字典序大哪个在前...
// 实际上也就是字符串比较
// 1. 使用 字符串数组 存储 数字 --> 因为本题的排序是基于“字符串”而不是“数值”
// 2. 定义比较函数 --> 按照 字符串 进行比较 --> 啊+ b 与 b + a 字符串相加， 哪个字典序大哪个在前 --> 注意：字符串比较是从第一位向最后一位比较，大的在前
// 3. 输出 字符串数组 中 所有 元素的 字符串
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;// 定义比较函数
bool cmp( string a, string b ){return a + b > b + a; // 相加 在再比较 --> 大的在前 我刚开始就写错了，写成了 a > b 因为是相加后最大的，所以比较的时候也要进行相加
}
int main( void ){string arr[ 20 ]; // 存放 <= 20 个字符串int n; // 输入的字符串的个数cin >> n; // 输入字符串的个数// 输入字符串for( int i = 0; i < n; i ++ ){cin >> arr[ i ];}sort ( arr, arr + n, cmp ); // 按字符串比较 大的在前// 打印字符串for( int i = 0; i < n; i ++ ){cout << arr[ i ];}cout << endl;return 0;
}