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

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

简单题 一封奇怪的信

1. 初始化：
   • 使用一个映射 map[rune]int 存储每个字母的宽度。
   • 初始化变量 row 和 length，分别表示当前行数和当前行的宽度。
2. 遍历字符串：
   • 对于字符串中的每个字符：
     • 检查当前行的宽度加上该字符的宽度是否超过 100。
     • 如果未超过，则将字符宽度累加到当前行。
     • 如果超过，则换行（增加行数），并将当前字符宽度作为新行的起始宽度。
3. 输出结果：
   • 遍历完成后，row 表示总行数，length 表示最后一行的宽度。

package main

import "fmt"

func main() {
	width := make(map[rune]int)
	for c := 'a'; c <= 'z'; c++ {
		var w int
		fmt.Scan(&w)
		width[c] = w
	}
	var s string
	fmt.Scan(&s)
	row, length := 1, 0
	for _, c := range s {
		if length+width[c] <= 100 {
			length += width[c]
		} else {
			length = width[c]
			row++
		}
	}
	fmt.Println(row, length)
}

中等题 小球投盒

1. 核心观察：
   • 使用 map[int]bool 记录哪些盒子已经有小球。
   • 对于第二种操作（向除了编号为 x 的其他盒子放入小球），可以通过跟踪一个变量 exp 来标记“唯一可能没有小球的盒子”。
2. 关键点：
   • 如果某个盒子被直接放入小球（操作 1），则该盒子一定有小球。
   • 如果执行了多次第二种操作（操作 2），且每次的 x 不同，则所有盒子最终都会被填充。
   • 如果在某次操作后发现所有盒子都已填充，则立即返回当前操作的编号。

package main

import "fmt"

func main() {
	var n, m int
	fmt.Scan(&n, &m)
	box := make(map[int]bool)
	exp := -1
	for i := 1; i <= m; i++ {
		var op, x int
		fmt.Scan(&op, &x)
		switch op {
		case 1:
			box[x] = true
		case 2:
			if exp == -1 {
				exp = x
			} else if exp != x {
				fmt.Println(i)
				return
			}
		}
		if len(box) == n || (exp != -1 && box[exp]) {
			fmt.Println(i)
			return
		}
	}
	fmt.Println(-1)
}

困难题 请客吃饭

1. 核心观察：
   • 隔阂值由财富值的最大差值决定，因此可以通过排序来简化计算。
   • 使用双指针法（滑动窗口）在排序后的数组中寻找满足条件的最小隔阂值。
2. 关键点：
   • 将朋友按财富值从小到大排序。
   • 维护一个滑动窗口，窗口内的朋友总愉悦值至少为 k。
   • 计算窗口内最大财富值与最小财富值的差值，并更新最小隔阂值。

package main

import (
	"fmt"
	"math"
	"sort"
)

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func main() {
	var (
		n int
		k int64
	)
	fmt.Scan(&n, &k)
	p := make([]struct {
		a int
		b int64
	}, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&p[i].a)
	}
	for i := 0; i < n; i++ {
		fmt.Scan(&p[i].b)
	}
	sort.Slice(p, func(i, j int) bool {
		return p[i].a < p[j].a
	})
	ans := math.MaxInt
	j, happiness := -1, int64(0)
	for i := 0; i < n; i++ {
		for j+1 < n && happiness < k {
			j++
			happiness += p[j].b
		}
		if happiness >= k {
			ans = min(ans, p[j].a-p[i].a)
		}
		happiness -= p[i].b
	}
	if ans == math.MaxInt {
		fmt.Println(-1)
	} else{
		fmt.Println(ans)
	}
}