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

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

简单题 分组

根据题目要求，需要计算n个同学最多可以分成多少个至少3人的组。由于每组至少需要3人，所以最多可以分成的组数就是n/3（向下取整）

package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	fmt.Println(n/3)
}

中等题 小欧的数组修改

1. 输入处理：

   • 首先读入一个整数 n，表示序列长度
   • 使用 map 存储每个数字出现的次数

2. 统计最大频次：

   • 遍历 map，找出序列中出现次数最多的数字的频次（ans）

3. 结果判断：

   • 如果最大频次 ans 等于序列长度 n，说明序列中全是相同的数字
     • 此时输出 n
   • 否则，输出 ans + 1
     • 因为我们可以通过修改一个数字，使得出现次数最多的数字的频次增加 1

package main

import "fmt"

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	var n int
	fmt.Scan(&n)
	mp := make(map[int]int)
	for i := 0; i < n; i++ {
		var a int
		fmt.Scan(&a)
		mp[a]++
	}
	var ans int
	for _, v := range mp {
		ans = max(ans, v)
	}
	if ans == n {
		fmt.Println(n)
	} else {
		fmt.Println(ans + 1)
	}
}

困难题 合唱队形

1. 输入处理：

   • 读入整数 n，表示队列人数
   • 读入 n 个整数，表示每个人的身高

2. 计算最长上升子序列（dp1）：

   • 正向遍历，计算以每个位置结尾的最长上升子序列长度
   • dp1[i] 表示以第 i 个人为结尾的最长上升子序列长度
   • 对每个位置 i，检查其前面所有位置 j
   • 如果 a[i] > a[j]，则可以接在 j 后面形成更长的上升序列

3. 计算最长下降子序列（dp2）：

   • 反向遍历，计算以每个位置开头的最长下降子序列长度
   • dp2[i] 表示以第 i 个人为开头的最长下降子序列长度
   • 对每个位置 i，检查其后面所有位置 j
   • 如果 a[i] > a[j]，则可以在 i 前面接入形成更长的下降序列

4. 计算最终结果：

   • 遍历每个位置 i，计算 dp1[i] + dp2[i] - 1（减 1 是因为位置 i 被计算了两次）
   • 记录最大值作为能形成的最长合唱队形
   • 用总人数 n 减去最长合唱队形的长度，得到需要出列的最少人数

package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	a := make([]int, n+1)
	for i := 1; i <= n; i++ {
		fmt.Scan(&a[i])
	}
	dp1 := make([]int, n+1)
	for i := 1; i <= n; i++ {
		dp1[i] = 1
		for j := 1; j <= i-1; j++ {
			if a[i] > a[j] {
				if dp1[j]+1 > dp1[i] {
					dp1[i] = dp1[j] + 1
				}
			}
		}
	}

	dp2 := make([]int, n+1)
	for i := n; i >= 1; i-- {
		dp2[i] = 1
		for j := n; j >= i+1; j-- {
			if a[i] > a[j] {
				if dp2[j]+1 > dp2[i] {
					dp2[i] = dp2[j] + 1
				}
			}
		}
	}

	ans := 0
	for i := 1; i <= n; i++ {
		if dp1[i]+dp2[i]-1 > ans {
			ans = dp1[i] + dp2[i] - 1
		}
	}

	fmt.Println(n - ans)
}