首页程序设计基础R - 2024 级程序设计基础复习赛
时间限制 内存限制
300 ms 65536 KB

# 题目描述

请注意本题的时间限制。

给出一个长度为 nn 的数列 a1,a2,⋯,ana_1,a_2,⋯,a_n，请你求出其中最小的 KK 个数。

# 输入格式

第一行，两个整数 n,K(1≤K≤5,K≤n≤106)n,K(1≤K≤5,K≤n≤10^6) 含义如上。

第二行，nn 个由空格分隔的整数 a1,a2,⋯,ana_1,a_2,⋯,a_n，保证 −2^{31}^≤a_i≤2^{31}−1。

# 输出格式

一行，KK 个由空格分隔的整数，表示数列 a1,a2,⋯,ana_1,a_2,⋯,a_n 中最小的 KK 个数（从小到大排序）。

# 输入样例

10 3
18 2 16 52 10 1 9 41 5 61

# 输出样例

1 2 5

# 提示

并不需要对整个数组进行排序，只需找出最小的 KK 个数即可。想一想冒泡排序？

# 题解：冒泡排序

根据提示，我们回想起冒泡排序进行完 ii 轮之后，已经选出了最大 / 小的 ii 个数并排好了序，这道题的 KK 都很小，所以我们进行 KK 轮冒泡排序即可。

时间复杂度：O(KN)O(KN)。

参考代码：

#include <stdio.h>
int n, k, a[1000010];
void Swap(int *a, int *b)
{
    int t = *a;
    *a = *b;
    *b = t;
    return;
}
int main()
{
    // freopen("Z.in", "r", stdin);
    // freopen("Z.out", "w", stdout);
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; ++ i)
        scanf("%d", &a[i]);
    
    for (int i = 1; i <= k; ++ i)
        for (int j = n; j >= i; -- j)
            if (a[i] > a[j])
                Swap(a + i, a + j);
    
    for (int i = 1; i <= k; ++ i)
        printf("%d ", a[i]);
    return 0;
}