p1923 【深基9.例4】求第 k 小的数
时间: 2023-04-28 22:01:52 浏览: 80
题目描述:
给定一个长度为 n 的数列,求其中第 k 小的数。
输入格式:
第一行包含两个整数 n 和 k。
第二行包含 n 个整数(所有整数均在 1∼10^9 范围内),表示整个数列。
输出格式:
输出一个整数,表示数列中第 k 小的数。
输入样例:
5 3
2 4 1 5 3
输出样例:
3
算法1:
暴力枚举
时间复杂度:O(n^2)
C++ 代码
算法2:
快速排序
时间复杂度:O(nlogn)
C++ 代码
算法3:
归并排序
时间复杂度:O(nlogn)
C++ 代码
算法4:
堆排序
时间复杂度:O(nlogn)
C++ 代码
算法5:
快速选择
时间复杂度:O(n)
C++ 代码
相关问题
p5721 【深基4.例6】数字直角三角形
题目描述:
给定一个正整数 $n$,输出一个数字直角三角形,其中直角边长度为 $n$,数字从 $1$ 到 $n^2$,按行从左到右,从上到下依次填入。
输入格式:
一个正整数 $n$。
输出格式:
输出数字直角三角形,每个数字占 $4$ 个字符宽度,每行末尾不能有多余空格。
输入样例:
5
输出样例:
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25
解题思路:
本题需要输出一个数字直角三角形,可以使用二维数组来存储数字,然后按照题目要求输出即可。
具体实现可以使用两个循环,第一个循环控制行数,第二个循环控制列数,然后根据行数和列数计算出当前位置应该填入的数字,最后按照题目要求输出即可。
代码实现:
p5712 【深基3.例4】apples
题目描述:
有 $n$ 个苹果,现在要将它们分成 $k$ 堆,每堆至少有一个苹果,求共有多少种分法。
输入格式:
输入一行包含两个整数 $n$ 和 $k$。
输出格式:
输出一个整数,表示总方案数,答案对 $10^9+7$ 取模。
数据范围:
$1≤n,k≤100$
输入样例:
```
7 3
```
输出样例:
```
35
```
解题思路:
这道题是一道典型的组合数学问题,可以用组合数公式来求解。
首先,我们可以将 $n$ 个苹果分成 $k$ 堆的方案数表示为 $f(n,k)$,那么我们可以考虑第 $n$ 个苹果的去向,它可以放在已有的某一堆中,也可以新开一堆,那么我们可以列出递推式:
$$
f(n,k)=f(n-1,k-1)+f(n-k,k)
$$
其中,$f(n-1,k-1)$ 表示第 $n$ 个苹果新开一堆,$f(n-k,k)$ 表示第 $n$ 个苹果加入已有的某一堆。
边界条件为:
$$
f(n,1)=1
$$
$$
f(n,k)=(n<k)
$$
最终答案为 $f(n,k)$。
需要注意的是,由于答案可能会很大,所以需要对 $10^9+7$ 取模。
C++ 代码