2024.5.1 计算机基础（快速排序）+算法（最小生成树）

计算机基础

题目

排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一 “趟”。下列排序中，不可能是快速排序第二趟结果的是（）【2019 年全国试题 10（2 分）】

A. 5, 2, 16, 12, 28, 60, 32, 72

B. 2, 16, 5, 28, 12, 60, 32, 72

C. 2, 12, 16, 5, 28, 32, 72, 60

D. 5, 2, 12, 28, 16, 32, 72, 60

题解

答案：D，分析如下。

每经过一趟快排，轴点元素都必然就位。也就是说，一趟下来至少有 1 个元素在其最终位置。所以考察各个选项，看有几个元素就位即可。

最终排序位置是：2, 5, 12, 16, 28, 32, 60, 72，而选项中正确的位置有：

A. 5, 2, 16, 12, 28, 60, 32, 72

B. 2, 16, 5, 28, 12, 60, 32, 72

C. 2, 12, 16, 5, 28, 32, 72, 60

D. 5, 2, 12, 28, 16, 32, 72, 60

• 第一趟排序，确定一个元素位置
• 第二趟排序，又确定一个或两个元素位置
  • 当第一趟元素确认的位置为最左或最右时，第二趟排序只能确认一个位置（A，B 选项情况）
  • 当第一趟元素确认位置不是最左或最右时，第二趟能确认 2 个位置（C 选项情况）

所以，两趟排序共确认 2 或 3 个元素位置。

算法

题目链接

垃圾佬抓宠物

不过，垃圾佬发现，这个网游的抓宠物系统是这样设定的：

抓特定的某种宠物需要花费特定的魔法豆。

另外，还可以通过一种宠物的呼唤能力来抓取另一种宠物，当然，要让宠物发挥它的呼唤能力需要两个条件：

第一，它要是你的宠物……人家还野生呢总不会听你的话陷害好友吧。

第二，你需要喂给你的宠物一定的魔法豆，它才有力气施展它的能力。

当另一只宠物被呼唤过来之后，你不费什么力气就可以把它抓住，也就不必再向系统付额外的魔法豆了。

注意，一种宠物能呼唤另一种宠物是因为他们心灵相通，所以如果A宠物能呼唤B宠物，那么B宠物也一定能呼唤A宠物。

而且，垃圾佬仔细研究之后发现，可能是OWO的程序员懒得再设置数据，A 宠物呼唤B宠物需要的魔法豆和B宠物呼唤A宠物需要的魔法豆是相等的。

垃圾佬的目标，当然是要算出最少要花费多少魔法豆啦~

垃圾佬拿出纸笔，算啊算啊算啊算，就在垃圾佬算出来的一刹那，静静温柔的对垃圾佬说：“Darling，你会不会觉得我很败家啊……其实我也知道我不应该用你的钱来冲魔法豆的”

垃圾佬心中一喜，抬头看着静静，静静说：“要不你不用抓齐，少抓一只吧。”

Input

第一行一个数字n，代表网游里一共有n 种宠物。

第二行有n 个数字，用空格隔开，依次说明直接抓取第1，2，3，4……n 种宠物需要多

少魔法豆

第三行一个C，表示游戏一共设定了C 对宠物心灵相通，可以互相呼唤。

接下来C 行，每行都有三个数字a，b 和w。代表第a 种和第b 种宠物可以互相呼唤，

呼唤前需要给a 宠物或b 宠物喂w 魔法豆。

n≤250，n∈N+

0<=c<=n*(n-1)/2

所有数字（含结果）<2^31

Output

只有一行，满足MM 需求最少要花费多少魔法豆

样例1

Input 
3
10 10 10
3
1 2 7
1 3 1
2 3 3

Output
11

样例说明：
先抓第一只，然后用第一只呼唤第三只。

仔细一看，是加一个源点的最小生成树。对于每一个删的节点进行枚举，因为n很小。

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

// 定义一个结构体用于存储边的信息：起点、终点和边的权重
struct node {
    int x, y;
    long long cost; // cost存路程
};

// 用于查找节点x所在的集合的代表元素
int fi(int x) {
    return x == fa[x] ? x : fa[x] = fi(fa[x]);
}

// 用于比较两个节点结构体的大小，按照cost进行排序
bool cmp(node a, node b) {
    return a.cost < b.cost; // 找路程小的
}

// 合并两个节点x和y所在的集合
void unio(int x, int y) {
    int p1 = fi(x), p2 = fi(y);
    if (p1 != p2) fa[p1] = p2;
}

// 主要的解法函数
void solve() {
    int n, m;
    while (cin >> n) {
        int ans = ~0U >> 1; // ans初始化为无穷大
        int v[maxn], fa[maxn]; // v数组和fa数组
        node Q[maxn]; // 存储边的数组

        // 读取顶点的数值和边的数量
        for (int i = 1; i <= n; i++) scanf("%d", &v[i]);
        scanf("%d", &m);

        // 读取每条边的信息
        for (int i = 1; i <= m; i++)
            scanf("%d%d%d", &Q[i].x, &Q[i].y, &Q[i].cost);

        // 将顶点的数值作为边加入到边的数组中
        for (int i = 1; i <= n; i++) {
            Q[i + m].x = 0;
            Q[i + m].y = i;
            Q[i + m].cost = v[i];
        }

        // 对边进行排序，优先选择权重小的边
        sort(Q + 1, Q + 1 + m, cmp);

        // 尝试每一种顶点作为起点
        for (int j = 1; j <= n; j++) {
            int sum = 0; // 初始化总权重为0
            for (int i = 0; i < n; i++) fa[i] = i; // 初始化每个节点所在集合的代表元素为自己

            // 遍历所有边，如果边的起点或终点是j，则跳过
            for (int i = 1; i <= m; i++) {
                if (Q[i].x == j || Q[i].y == j) continue;
                if (fi(Q[i].x) == fi(Q[i].y)) // 如果两个节点已经在同一个集合中，则跳过
                    continue;
                unio(Q[i].x, Q[i].y); // 合并两个节点所在的集合
                sum += Q[i].cost; // 累加权重
            }
            ans = min(ans, sum); // 更新最小权重和
        }
        cout << ans << endl; // 输出最小权重和
    }
}

// 主函数
int main() {
    int t = 1; // 测试用例个数
    for (int cas = 1; cas <= t; cas++) {
        solve(); // 调用解法函数
    }
}

最小生成树 - OI Wiki

是的，这段代码采用的最小生成树算法是基于 Prim 算法的变种。Prim 算法是一种用于寻找图的最小生成树的算法，它通过逐步增加边来构建最小生成树，直到所有需要连接的顶点都被包含在内。在每步中，它都会选择连接树与非树顶点间权重最小的边，将其添加到最小生成树中。
以下是代码中体现 Prim 算法的几个关键点：

1. 初始化：ans 用于记录最小生成树的总权重，初始设为无穷大。fa 数组用于记录并查集的父节点，初始时每个节点的父节点都是自己，表示每个节点独立。
2. 排序：将所有的边按照权重进行排序，这样可以选择最小的边添加到生成树中。
3. 循环：对于每个顶点 j，都尝试将其作为最小生成树的一个起点。
4. 并查集：使用 fi 函数（查找代表元素）和 unio 函数（合并两个节点所在的集合）来维护并查集，以快速判断两个节点是否已经在同一棵树中。
5. 权重累加：对于排序后的每条边，如果边的两个顶点不在同一棵树中，则将这条边添加到最小生成树中，并通过 sum += Q[i].cost 累加其权重。
6. 最小权重更新：在每次循环结束后，使用 ans = min(ans, sum) 来更新最小生成树的总权重。

代码通过重复这个过程来找到所有顶点的最小生成树，并输出最小的总权重。这种处理方式是 Prim 算法的典型实现。