有三种葡萄,每种分别有a,b,c颗,有三个人,第一个只吃第一种和第二种葡萄,第二个人只吃第二种和第三种葡萄,第三个人只吃第一种和第三种葡萄。
适当安排三个人使得吃完所有葡萄,并且三个人中吃的最多的那个人吃得尽量少。
输入描述:
第一行数字T,代表数据组数
接下来T行,每行三个数a,b,c,数字用空格间隔
1 <= a, b, c <= 108,1 <= T <= 10
输出描述:
对于每组数据,输出一行一个数字表示三个人中吃的最多的那个人吃的数量。
例如:
输入
2
1 2 3
1 2 6
输出
2
3
尝试用Golang解决:
package main
import (
"bufio"
"fmt"
"io"
"os"
"strconv"
"strings"
)
func readStdin() (lines []string) {
reader := bufio.NewReader(os.Stdin)
for {
line, err := reader.ReadString('\n')
if err != io.EOF {
lines = append(lines, line)
} else {
break
}
}
return
}
func maxKey(m map[string]int) (key string) {
maxValue := 0
for k, v := range m {
if v >= maxValue {
maxValue = v
key = k
}
}
return
}
func solve(slice []string) (num int) {
fMap := make(map[string]int)
for i, s := range slice {
n, _ := strconv.Atoi(s)
switch i {
case 0:
fMap["a"] = n
case 1:
fMap["b"] = n
case 2:
fMap["c"] = n
}
}
rMap := map[string][2]string{
"a": {"1", "3"},
"b": {"1", "2"},
"c": {"2", "3"},
}
pMap := map[string]int{"1": 0, "2": 0, "3": 0}
for fMap["a"]+fMap["b"]+fMap["c"] > 0 {
key := maxKey(fMap)
fMap[key]--
switch key {
case key:
if pMap[rMap[key][0]] < pMap[rMap[key][1]] {
pMap[rMap[key][0]]++
} else {
pMap[rMap[key][1]]++
}
}
}
num = pMap[maxKey(pMap)]
return
}
func main() {
lines := readStdin()
for i, line := range lines {
if i != 0 {
line = strings.Replace(line, "\n", "", -1)
line = strings.Replace(line, "\r", "", -1)
slice := strings.Split(line, " ")
num := solve(slice)
fmt.Println(num)
}
}
}
结果是:
您的代码已保存
运行超时:您的程序未能在规定时间内运行结束,请检查是否循环有错或算法复杂度过大。
case通过率为60.00%
看来用字典加循环的方式来处理还是过于具体了,数据量过大时效率太低,不够抽象;回头还得找一个新的办法来解决。
有疑问加站长微信联系(非本文作者)