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：
来自左程云。
大体步骤如下：
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(), " 毫秒")
}
