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(m*n*log(m))，空間復雜度為O(m)。
# go完整代碼如下：
```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(), " 毫秒")
}
```
