牛客周赛 09 · 平均数
T1. 小美的外卖订单编号
- 标签：位运算
T2. 小美的加法
- 标签：枚举
T3. 小美的01串翻转
- 标签：枚举
T4. 小美的数组操作
- 标签：脑筋急转弯、排序
T1. 小美的外卖订单编号
<https://ac.nowcoder.com/acm/problem/258416>
题解（位运算）
题目定义的编号是 base 1 的，而取模运算是 base 0 的，当编号正好是 mod 的整数倍是会出错。这里有一个技巧，我们可以先对编号偏移到 base 0 取模，最后再偏移回来。
fun main(args: Array<String>) {
repeat(nextInt()) {
val m = nextInt()
val x = nextInt()
println((x - 1) % m + 1)
}
done()
}
复杂度分析：
- 时间复杂度：O(1)
- 空间复杂度：O(1)
T2. 小美的加法
<https://ac.nowcoder.com/acm/problem/258422>
题解（枚举）
在每个方案中，我们需要选择一组相邻元素做乘法，而剩余元素做加法。一开始用前缀和求前后两段加法的值，其实没必要，只需要从整体和 sum 中减去做乘法的两个元素就好了。
fun main(args: Array<String>) {
val n = nextInt()
val nums = nextArrayI(n)
val sum = nums.fold(0L) { it, arr -> it + arr }
var ret = sum
for (i in 1 until n) {
ret = max(ret, sum - nums[i] - nums[i - 1] + 1L * nums[i] * nums[i - 1])
}
println(ret)
done()
}
复杂度分析：
- 时间复杂度：O(n) 预处理整体和和枚举的时间都是 O(n)；
- 空间复杂度：O(n) nums 数组空间。
T3. 小美的01串翻转
<https://ac.nowcoder.com/acm/problem/258418>
题解一（枚举）
枚举所有起点开始的子串，求出以 0 开头或以 1 开头的最小权值，并累加到结果中。
写法 1：
fun main(args: Array<String>) {
val str = nextString()
var ret = 0
for (i in 0 until str.length) {
var c0 = 0
var c1 = 0
for (j in i until str.length) {
if ((str[j] == '0' && (j - i) % 2 == 0) || (str[j] == '1' && (j - i) % 2 == 1)) {
c0++
} else {
c1++
}
ret += min(c0, c1)
}
}
println(ret)
done()
}
写法 2：
fun main(args: Array<String>) {
val str = nextString()
var ret = 0
for (i in 0 until str.length) {
var c0 = 0
var c1 = 0
for (j in i until str.length) {
c0 += if (str[j] == "01"[(j - i) % 2]) 1 else 0
c1 += if (str[j] == "10"[(j - i) % 2]) 1 else 0
ret += min(c0, c1)
}
}
println(ret)
done()
}
复杂度分析：
- 时间复杂度：O(n^2)
- 空间复杂度：O(1)
题解二（区间 DP）
- 定义： 定义 dp[i][j] 表示区间 [i, j] 的最小权值，考虑到以 0 或 1 开头的权值可能不同，再增加第三维度 [k] 表示以 0 和 1 结尾的最小权值；
- 转移： 对于 [i, j] 区间来说，可以从 [i, j - 1] 区间转移过来，对于字符 str[j] 来说，有转换和不转换两种选择，那么有： 转换：dp[i][j][x xor 1] = dp[i][j - 1][x] + 1不转换：dp[i][j][x] = dp[i][j - 1][x xor 1]
fun main(args: Array<String>) {
val str = nextString()
val n = str.length
var ret = 0
// dp[i][j][2] 表示 [i,j] 以 0 和 1 结尾的最小权值
val dp = Array(n) { Array(n) { IntArray(2) } }
for (i in 0 until n) {
dp[i][i][0] = if (str[i] == '0') 0 else 1
dp[i][i][1] = if (str[i] == '0') 1 else 0
}
for (len in 2..n) {
for (i in 0..n - len) {
val j = i + len - 1
val x = str[j] - '0'
dp[i][j][x] = dp[i][j - 1][x xor 1]
dp[i][j][x xor 1] = dp[i][j - 1][x] + 1
// println("len=$len, i=$i, j=$j, x=$x, sub=${str.substring(i, j + 1)} ${dp[i][j][x]}, ${dp[i][j][x xor 1]}")
ret += Math.min(dp[i][j][x], dp[i][j][x xor 1])
}
}
println(ret)
done()
}
复杂度分析：
- 时间复杂度：O(n^2) 一共有 n^2 个子状态，每个子状态的时间是 O(1)，动态规划整体时间复杂度是 O(n^2)；
- 空间复杂度：O(n^2) DP 数组空间。
T4. 小美的数组操作
<https://ac.nowcoder.com/acm/problem/258420>
题解（脑筋急转弯）
- 关键信息： 根据题目要求，我们需要以最少操作次数构造出最多数量的众数。其中「最多数量的众数」是优先的，即优先让数量更多，再考虑最少操作次数；
- 平均值： 题目操作可以分别对两个数加一和减一，最优情况下数组元素和能够被 n 整除时，能够构造最大众数。
- 局部平均： 如果无法构造完全平均，当选择一个数作为工具数，一定可以保证其他 n - 1 个数是平均的。此时，问题的关键在于选择哪些数（哪个数作为工具数）以及选哪个目标平均值。
1 | 123456 4 | 333333 -2 | 444444 ... -32 | 999999
- 中位数： 为了让操作数尽可能小，选择 n - 1 个数的平均值作为目标值是最优的。当不能整除时，要考虑左中位数和右中位数两种情况。
- 贡献度： 数组的最大值和最小值对平均值的贡献度是最大的，相应地也需要更多操作数，所以我们只需要考虑将最大值和最小值作为工具数的情况。
fun main(args: Array<String>) {
val n = nextInt()
val nums = nextArrayI(n)
var fullSum = nums.fold(0L) { it, arr -> it + arr }
fun count(nums: IntArray, from: Int, to: Int, target: Long): Long {
var c0 = 0L
var c1 = 0L
for (i in from..to) {
if (nums[i] < target) {
c0 += target - nums[i]
} else {
c1 += nums[i] - target
}
}
return max(c0, c1)
}
if (fullSum % n == 0L) {
// 全局平均
println(count(nums, 0, n - 1, fullSum / n))
} else {
// 局部平均
nums.sort()
val target1 = (fullSum - nums[0]) / (n - 1)
val target2 = (fullSum - nums[n - 1]) / (n - 1)
val choice1 = min(count(nums, 1, n - 1, target1), count(nums, 1, n - 1, target1 + 1))
val choice2 = min(count(nums, 0, n - 2, target2), count(nums, 0, n - 2, target2 + 1))
println(min(choice1, choice2))
}
done()
}
也可以提前判断取左中位数还是右中位数：
fun main(args: Array<String>) {
val n = nextInt()
val nums = nextArrayI(n)
var fullSum = nums.fold(0L) { it, arr -> it + arr }
...
if (fullSum % n == 0L) {
// 全局平均
println(count(nums, 0, n - 1, fullSum / n))
} else {
// 局部平均
nums.sort()
// 选择 1
var target1 = (fullSum - nums[0]) / (n - 1)
if ((fullSum - nums[0]) % (n - 1) > (n - 1) / 2) target1++
val count1 = count(nums, 1, n - 1, target1)
// 选择 2
var target2 = (fullSum - nums[n - 1]) / (n - 1)
if ((fullSum - nums[n - 1]) % (n - 1) > (n - 1) / 2) target2++
val count2 = count(nums, 0, n - 2, target2)
println(min(count1, count2))
}
done()
}
复杂度分析：
- 时间复杂度：O(nlgn) 瓶颈在排序；
- 空间复杂度：O(n) nums 数组空间。
