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

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

简单题 记负均正

1. 输入处理：

• 首先读入一个整数 n，表示有 n 个数字需要处理
• 用三个变量分别统计：
  • cntNeg：负数的个数
  • cntPos：正数的个数
  • sumPos：正数的和

2. 循环处理每个数字：

• 对于每个输入的数字 x：
  • 如果 x < 0，负数计数加1
  • 如果 x > 0，正数计数加1，同时累加到正数和中

3. 输出结果：

• 先输出负数的个数 cntNeg
• 然后输出正数的平均值：
  • 如果没有正数（cntPos = 0），输出 0
  • 否则，输出 sumPos/cntPos 的浮点数结果

package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	cntNeg := 0
	cntPos, sumPos := 0, 0

	for i := 0; i < n; i++ {
		var x int
		fmt.Scan(&x)
		if x < 0 {
			cntNeg++
		} else if x > 0 {
			cntPos++
			sumPos += x
		}
	}
	if cntPos == 0 {
		fmt.Println(cntNeg, 0)
	} else {
		fmt.Println(cntNeg, float64(sumPos)/float64(cntPos))
	}
}

中等题 小数字

只能将 n 趋向于 2

只能将 n 趋向于 1

而且上面两种方式可以在很少的操作次数内将 n 变为 1 或 2

因此当 n>=2 时，选择上面两种方式中得到的较小值，当 n < 2 时可以考虑 将 n 变为更小的数

package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
)

var (
	in  *bufio.Reader
	out *bufio.Writer
)

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

func solve() {
	var n, m int
	fmt.Fscan(in, &n, &m)
	for i := 0; i < m; i++ {
		if n < 2 {
			n -= m - i
			break
		}
		n = min(int(math.Ceil(math.Sqrt(float64(n)))), int(math.Ceil(float64(n)/2)))
	}
	fmt.Fprintln(out,n)
}

func main() {
	in = bufio.NewReader(os.Stdin)
	out = bufio.NewWriter(os.Stdout)
	defer out.Flush()
	var t int
	fmt.Fscan(in, &t)
	for i := 0; i < t; i++ {
		solve()
	}
}

困难题 【模板】完全背包

1. 定义状态

dp[i][j] 表示：前 i 个物品中选，恰好放进一个容量为 j 的背包里，所能获得的最大价值。

2. 初始化

​ • dp[0][0] = 0表示前 0 个物品，容量为 0 时，价值为 0。

​ • 其余所有 dp[i][j] 初始设为 math.MinInt（一个极小值），表示不可达。

3. 状态转移

遍历每个物品 i，每个容量 j，转移分为两种情况：

• 选 0 个第 i 个物品：

dp[i][j] = dp[i-1][j]

• 选多个第 i 个物品（前提是当前容量 j >= v[i]）：

dp[i][j] = max(dp[i][j], dp[i][j-v[i]] + w[i])

因为每个物品可以选多次，所以从 dp[i][j-v[i]] 转移。

4. 答案获取

• 遍历 dp[n][j] 中所有容量 j，取最大值就是背包能装的最大价值。
• dp[n][m] 就是若背包恰好装满m容量的最大价值。

package main

import (
	"fmt"
	"math"
)

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

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

	dp := make([][]int, n+1)
	for i := range dp {
		dp[i] = make([]int, m+1)
		for j := range dp[i] {
			dp[i][j] = math.MinInt
		}
	}
	dp[0][0] = 0
	for i := 1; i <= n; i++ {
		for j := 0; j <= m; j++ {
			if j < v[i] {
				dp[i][j] = dp[i-1][j]
			} else {
				dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]]+w[i])
			}
		}
	}
	ans := 0
	for j := 0; j <= m; j++ {
		ans = max(ans, dp[n][j])
	}
	fmt.Println(ans)
	fmt.Println(max(0, dp[n][m]))
}