牛客春招刷题训练营-2025.5.28题解

活动地址： 牛客春招刷题训练营 - 编程打卡活动

简单题 小红浏览论坛

1. 读入贴子数量 n 和最小差值 x
2. 对每个贴子读入点赞数 a 和反对数 b
3. 检查点赞数和反对数的差的绝对值是否大于等于 x
4. 统计满足条件的贴子数量并输出

package main

import "fmt"

func main() {
	var n, x int
	fmt.Scan(&n, &x)
	ans := 0
	for i := 0; i < n; i++ {
		var a, b int
		fmt.Scan(&a, &b)
		if a-b >= x || b-a >= x {
			ans++
		}
	}
	fmt.Println(ans)
}

中等题 游游的排列构造

步骤1：放置大数（先放 n-k+1 到 n 的数）

• 从索引 0 开始，每隔一个位置放置一个数
• 这样确保大数之间至少有一个数的间隔
• 使用偶数位置：0, 2, 4...

步骤2：填充剩余空位

• 用 1 到 n-k 的数字
• 填充到之前跳过的位置（奇数索引）

package main

import "fmt"

func main() {
	var n, k int
	fmt.Scan(&n, &k)
	a := make([]int, n)
	v := n - k + 1
	for i := 0; i < n; i += 2 {
		a[i] = v
		if v == n {
			break
		}
		v++
	}
	v = 1
	for i := range a {
		if a[i] == 0 {
			a[i] = v
			v++
		}
		fmt.Print(a[i], " ")
	}
}

困难题 【模板】最小生成树

1. 输入图的结构：
   • 图由顶点和边组成，边包含两个顶点和一个权重。
   • 使用结构体表示边，并将所有边存储在一个数组中。
2. 对边进行排序：
   • 按照边的权重从小到大排序。
3. 使用并查集管理连通性：
   • 并查集用于判断两个顶点是否已经连通。如果一条边的两个顶点已经连通，则跳过该边以避免形成环。
4. 构建最小生成树：
   • 遍历排序后的边，依次加入生成树中，直到生成树包含所有顶点。

package main

import (
	"fmt"
	"sort"
)

var (
	n, m  int
	fa    []int
	depth []int
)

type edge struct {
	id, u, v, w int
}

func initUnionFind(n int) {
	fa = make([]int, n+1)
	depth = make([]int, n+1)
	for i := 1; i <= n; i++ {
		fa[i] = i
		depth[i] = 1
	}
}

func find(x int) int {
	if x != fa[x] {
		fa[x] = find(fa[x])
	}
	return fa[x]
}

func unite(a, b int) {
	a, b = find(a), find(b)
	if depth[a] == depth[b] {
		depth[a]++
		fa[b] = a
	} else {
		if depth[a] < depth[b] {
			fa[a] = b
		} else {
			fa[b] = a
		}
	}
}

func same(a, b int) bool {
	return find(a) == find(b)
}

func main() {
	fmt.Scan(&n, &m)
	var edges []edge
	for i := 0; i < m; i++ {
		var u, v, w int
		fmt.Scan(&u, &v, &w)
		edges = append(edges, edge{i + 1, u, v, w})
	}

	sort.Slice(edges, func(i, j int) bool {
		return edges[i].w < edges[j].w
	})

	initUnionFind(n)

	kruskal := func() (res int, ids []int) {
		for _, e := range edges {
			if !same(e.u, e.v) {
				unite(e.u, e.v)
				res += e.w
				ids = append(ids, e.id)
			}
			if len(ids) == n-1 {
				break
			}
		}
		return
	}

	k, ids := kruskal()
	fmt.Println(k)
	for _, id := range ids {
		fmt.Print(id, " ")
	}
}