P16 Dota2参议院、优势洗牌[田忌赛马] (贪心)

冷不防 2022-08-29 09:47 183阅读 0赞

# 一、Dota2参议院 #

两派依序投票, 当前投票人可以将后续任意待投票人投票出局, 投完后此人的投票次序排至末尾, 直至当前所有投票人为统一派别为止;  
例如RDDDR(R将D投出,R排到末尾)->DDRR(D将R投出,D排至末尾)->DRD(D将R投出,D排至末尾)->DD, D派胜利

func dota2(array []string) (winner string) { 
    	length := len(array)
    	chR := make(chan int, length)
    	defer close(chR)
    	chD := make(chan int, length)
    	defer close(chD)
    	for i := 0; i < len(array); i++ { 
    		if array[i] == "R" { 
    			chR <- i
    		} else { 
    			chD <- i
    		}
    	}
    	var last int
    	for len(chD) != 0 && len(chR) != 0 { 
    		R := <-chR
    		D := <-chD
    		if R < D {  // R具有投票权
    			chR <- R + length
    			last = R + length
    		} else { 
    			chD <- D + length
    			last = D + length
    		}
    	}
    	return array[last%length]
    }
    
    func main() { 
    	fmt.Println("winner: ", dota2([]string{ "R", "D", "D", "D", "R"}))
    }

# 二、优势洗牌\[田忌赛马\] #

对决齐桓公马匹，每场比赛中，在剩余马匹里，田忌要么把最小优胜马找出来, 要么找匹垃圾马顶上

func derby(q, t []int) (array []int) { 
    	array = make([]int, len(q))            // 排好序的场次
    	selected := make(map[int]bool, len(q)) // 挑选过的马匹下标
    	for i := 0; i < len(q); i++ { 
    		/* 对决齐桓公马匹, 田忌要么把最小优胜马找出来, 要么找匹垃圾马顶上 */
    		var index, min = -1, math.MaxUint8   // 找剩余马匹的最小优胜马
    		var index2, min2 = -1, math.MaxUint8 // 找剩余马匹的最小垃圾马
    		for j := 0; j < len(t); j++ { 
    			if q[i] < t[j] && t[j] < min && !selected[j] {  // 田忌的马优胜 && 为最小值 && 之前没有被选过
    				min = t[j]
    				index = j
    			}
    			if t[j] < min2 && !selected[j] {  // 最小垃圾马 && 之前没被选过
    				min2 = t[j]
    				index2 = j
    			}
    		}
    		if index >= 0 {  // 田忌有马优胜
    			array[i] = min         // 将该马筛入对决场次
    			selected[index] = true // 将田忌该马移除剩余场次
    		} else {  //否则田忌没有优胜马, 将最小垃圾马顶上
    			array[i] = min2         // 将该马筛入对决场次
    			selected[index2] = true // 将田忌该马移除剩余场次
    		}
    	}
    	return
    }
    
    func main() { 
    	// 齐王
    	q := []int{ 16, 20, 10, 21, 18, 5}
    	// 田忌
    	t := []int{ 2, 4, 19, 17, 11, 9}
    	fmt.Println(derby(q, t))
    }

> \[17 2 11 4 19 9\]