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