2023-12-27：用 go 语言，店铺数量 n，编号 1~n，人的数量 m，编号 1~m，每个人有自己投票的店铺 p，和改投 1 号店的报价 x。返回想让 1 号店铺成为人气最高的店，至少花多少钱？ 1 ＜= p,

作者：福大大架构师每日一题

2023-12-27
北京
本文字数：2518 字
阅读完需：约 8 分钟

2023-12-27：用 go 语言，店铺数量 n，编号 1~n，

人的数量 m，编号 1~m，

每个人有自己投票的店铺 p，和改投 1 号店的报价 x。

返回想让 1 号店铺成为人气最高的店，至少花多少钱？

1 <= p,n,m <= 3000，

1 <= x <= 10^9。

1 号店铺贿赂问题。来自华为 OD。

答案 2023-12-27：

来自左程云。

灵捷3.5

大体步骤如下：

minCost1 算法步骤：

1.统计每个店铺对应的人数，存储在 cnts 数组中。

2.判断是否需要改变投票，若不需要改变，则返回 0。

3.调用 process 函数，传入 arr 数组、当前位置 i、店铺数量 n 和 change 数组。

4.在 process 函数中，判断是否遍历完所有人的投票，若是则进行以下操作：

4.a. 统计各店铺的人数，并计算贿赂费用 sum。

4.b. 检查是否存在店铺的人数超过 1 号店铺的人数，若存在则返回一个很大的值(math.MaxInt64)，否则返回贿赂费用 sum。

5.否则，继续调用 process 函数，分别传入改变当前位置 i 的投票和不改变的投票，并比较两种情况的最小贿赂费用。

minCost2 算法步骤：

1.统计每个店铺对应的人数，存储在 cnts 数组中。

2.判断是否需要改变投票，若不需要改变，则返回 0。

3.对 arr 数组按照报价 x 进行升序排序。

4.创建一个二维数组 shops，用于存储每个店铺对应的人的索引。

5.遍历 arr 数组，将每个人的索引添加到 shops 数组对应店铺的列表中。

6.创建一个表示人是否被使用的布尔数组 used，并初始化为 false。

7.初始化一个很大的值 ans 为 math.MaxInt64。

8.从 cnts[1]+1 开始，遍历可能的最小贿赂人数 i：

8.a.调用函数 f，传入 arr 数组、店铺数量 n、已贿赂人数 already、必须贿赂人数 must、shops 数组和 used 数组。

8.b.若返回值 money 不等于-1，则更新 ans 为 min(ans, money)。

9.返回最小贿赂费用 ans。

总的时间复杂度和空间复杂度：

minCost1 算法的时间复杂度为 O(2^m)，空间复杂度为 O(m)。
minCost2 算法的时间复杂度为 O(mnlog(m))，空间复杂度为 O(m)。

go 完整代码如下：

package main
import (  "fmt"  "math"  "math/rand"  "sort"  "time")
func minCost1(n, m int, arr [][]int) int {  cnts := make([]int, n+1)  for _, p := range arr {    cnts[p[0]]++  }  needChange := false  for i := 2; i <= n; i++ {    if cnts[i] >= cnts[1] {      needChange = true      break    }  }  if !needChange {    return 0  }  return process(arr, 0, n, make([]bool, m))}
func process(arr [][]int, i, n int, change []bool) int {  if i == len(arr) {    cnts := make([]int, n+1)    sum := 0    for j := 0; j < len(arr); j++ {      if change[j] {        cnts[1]++        sum += arr[j][1]      } else {        cnts[arr[j][0]]++      }    }    ok := true    for j := 2; j <= n; j++ {      if cnts[j] >= cnts[1] {        ok = false        break      }    }    if !ok {      return math.MaxInt64    } else {      return sum    }  } else {    p1 := math.MaxInt64    if arr[i][0] != 1 {      change[i] = true      p1 = process(arr, i+1, n, change)      change[i] = false    }    p2 := process(arr, i+1, n, change)    return min(p1, p2)  }}
func minCost2(n, m int, arr [][]int) int {  cnts := make([]int, n+1)  for _, p := range arr {    cnts[p[0]]++  }  needChange := false  for i := 2; i <= n; i++ {    if cnts[i] >= cnts[1] {      needChange = true      break    }  }  if !needChange {    return 0  }  sort.Slice(arr, func(i, j int) bool {    return arr[i][1] < arr[j][1]  })  shops := make([][]int, n+1)  for i := 0; i <= n; i++ {    shops[i] = []int{}  }  for i := 0; i < m; i++ {    shops[arr[i][0]] = append(shops[arr[i][0]], i)  }  used := make([]bool, m)  ans := math.MaxInt64  for i := cnts[1] + 1; i <= m; i++ {    money := f(arr, n, cnts[1], i, shops, used)    if money != -1 {      ans = min(ans, money)    }  }  return ans}
func f(arr [][]int, n, already, must int, shops [][]int, used []bool) int {  for i := 0; i < len(used); i++ {    used[i] = false  }  sum := int(0)  for i := 2; i <= n; i++ {    needChange := max(0, len(shops[i])-must+1)    for j := 0; j < needChange; j++ {      people := shops[i][j]      sum += int(arr[people][1])      used[people] = true    }    already += needChange    if already > must {      return -1    }  }  for i, j := 0, 0; already+j < must; i++ {    if arr[i][0] != 1 && !used[i] {      sum += arr[i][1]      j++    }  }  return sum}
func randomArray(len, n, v int) [][]int {  arr := make([][]int, len)  for i := 0; i < len; i++ {    arr[i] = []int{      rand.Intn(n) + 1,      rand.Intn(v) + 1,    }  }  return arr}
func min(a, b int) int {  if a < b {    return a  }  return b}
func max(a, b int) int {  if a > b {    return a  }  return b}
func main() {  rand.Seed(time.Now().Unix())  N := 10  M := 16  V := 100  testTimes := 10000
  fmt.Println("测试开始")  for i := 0; i < testTimes; i++ {    n := rand.Intn(N) + 1    m := rand.Intn(M) + 1    arr := randomArray(m, n, V)    ans1 := minCost1(n, m, arr)    ans2 := minCost2(n, m, arr)    if ans1 != ans2 {      fmt.Println("出错了!")      fmt.Println("n : ", n)      fmt.Println("m : ", m)      for _, p := range arr {        fmt.Println(p[0], " , ", p[1])      }      fmt.Println(ans1)      fmt.Println(ans2)      break    }  }  fmt.Println("测试结束")
  n := 3000  m := 3000  v := 1000000000  arr := randomArray(n, m, v)  start := time.Now()  minCost2(n, m, arr)  end := time.Now()  fmt.Println("最大数据量时的运行时间 : ", end.Sub(start).Milliseconds(), " 毫秒")}