2023-12-27：用go语言，店铺数量n，编号1~n， 人的数量m，编号1~m， 每个人有自己投票的店铺p，和改投1号店的报

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

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

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

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

1 <= p,n,m

1 <= x

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(), " 毫秒")

}

在这里插入图片描述