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

简单题循环求和

分组思考：
- 每两个连续的数字（一个奇数和一个偶数）可以看作一组。
- 每组的和是固定的，即 -1（奇数减去紧随其后的偶数）或者 1（奇数减去紧随其前的偶数）。
具体实现步骤：
- 计算区间 [l, r] 的长度：length = r - l + 1。
- 根据长度判断是否可以整除 2：
  - 当l为奇数时：每组的和为 -1
    - 如果r为奇数：则需要额外处理最后一个数字
    - 如果r为偶数：则所有数字都成对分组
  - 当l为偶数时：每组的和为 1
    - 如果r为奇数：则所有数字都成对分组，
    - 如果r为偶数：则需要额外处理最后一个数字
- 对于最后一个数字，判断它是奇数还是偶数，并将其加入总和。

package main

import "fmt"

func solve() {
	var l, r int64
	fmt.Scan(&l, &r)
	length := r - l + 1
	if l%2 == 1 {
		if r%2 == 1 {
			fmt.Println(-length/2 + r)
		} else {
			fmt.Println(-length / 2)
		}
	} else {
		if r%2 == 0 {
			fmt.Println(length/2 - r)
		} else {
			fmt.Println(length / 2)
		}
	}
}

func main() {
	var t int
	fmt.Scan(&t)
	for i := 0; i < t; i++ {
		solve()
	}
}

中等题小美走公路

因为公路是环形的，所以有两条可能的路径：
1. 按顺时针方向从 x 到 y 的距离。
2. 按逆时针方向从 x 到 y 的距离（即从 y 到 x 的顺时针距离）。
  
  其中逆时针路径的距离等于总距离 sum 减去顺时针路径的距离 ans。
最短距离就是这两条路径中较短的一个。

package main

import "fmt"

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

func main() {
	var n int
	fmt.Scan(&n)
	a := make([]int64, n+1)
	sum := int64(0)
	for i := 1; i <= n; i++ {
		fmt.Scan(&a[i])
		sum += a[i]
	}
	var x, y int
	fmt.Scan(&x, &y)
	if x > y {
		x, y = y, x
	}
	ans := int64(0)
	for i := x; i <= y-1; i++ {
		ans += a[i]
	}
	fmt.Println(min(sum-ans, ans))
}

困难题游游的除2操作

观察操作效果：
- 每次操作实际上是将一个数不断减小，直到它变为 0 或与其他数相等。
- 如果我们希望所有元素最终相等，那么目标值一定是数组中某个数经过若干次操作后的结果。
关键点：
- 最终相等的值一定是数组中某个元素通过多次操作得到的结果。换句话说，目标值是数组中某个元素的“祖先”。
- 我们可以通过对每个元素进行模拟操作，记录它们的所有可能值，找到一个公共的目标值，使得所有元素都能通过最少的操作次数达到这个值。
算法步骤：
- 对于数组中的每个元素，模拟将其不断除以 2 的过程，记录下它在每一步的值。
- 统计每个值出现的次数（即有多少个元素可以通过操作变成这个值）。
- 找到一个值，使得所有元素都能通过最少的操作次数变成这个值。

package main

import (
	"fmt"
	"math"
)

func minOperationsToTarget(x, target int) int {
	operations := 0
	for x > target {
		x /= 2
		operations++
	}
	return operations
}

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

	valueCount := make(map[int]int)
	for _, num := range a {
		current := num
		for current > 0 {
			valueCount[current]++
			current /= 2
		}
	}

	minOps := math.MaxInt
	for value, count := range valueCount {
		if count == n {
			totalOps := 0
			for _, num := range a {
				totalOps += minOperationsToTarget(num, value)
			}
			if totalOps < minOps {
				minOps = totalOps
			}
		}
	}
	fmt.Println(minOps)
}

#牛客春招刷题训练营#

牛客春招刷题训练营文章被收录于专栏

爱丽姐真是太好了