牛客春招刷题训练营-2025.5.28题解
活动地址: 牛客春招刷题训练营 - 编程打卡活动
简单题 小红浏览论坛
- 读入贴子数量
n
和最小差值x
- 对每个贴子读入点赞数
a
和反对数b
- 检查点赞数和反对数的差的绝对值是否大于等于
x
- 统计满足条件的贴子数量并输出
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], " ")
}
}
困难题 【模板】最小生成树
- 输入图的结构:
- 图由顶点和边组成,边包含两个顶点和一个权重。
- 使用结构体表示边,并将所有边存储在一个数组中。
- 对边进行排序:
- 按照边的权重从小到大排序。
- 使用并查集管理连通性:
- 并查集用于判断两个顶点是否已经连通。如果一条边的两个顶点已经连通,则跳过该边以避免形成环。
- 构建最小生成树:
- 遍历排序后的边,依次加入生成树中,直到生成树包含所有顶点。
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, " ")
}
}
#牛客春招刷题训练营#牛客春招刷题训练营 文章被收录于专栏
爱丽姐真是太好了