吃葡萄

CancerTiN · · 1088 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

有三种葡萄,每种分别有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%

看来用字典加循环的方式来处理还是过于具体了,数据量过大时效率太低,不够抽象;回头还得找一个新的办法来解决。


有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:CancerTiN

查看原文:吃葡萄

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

1088 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传