/*
*最小容量
详细描述
有n(1<=n<=100000)件重量为w1，w2...wn (1<=wi<=100000)的物品，小S有m(1<=m<=n)个袋子，每个袋子的容量上限是k。

已知n，w1，w2...wn和m，求最小的k。 小S一定是按w1到wn顺序进行打包。



比如：

n=4

m=2

w1,w2,w3,w4 = 4, 2, 3, 1

其中一种方案：

第一个袋子装 w1和w2，重量是6

第二个袋子装w3和w4，重量是4

所以袋子的容量上限最小是6
*/
func Solve(n int, m int, weights []int) int64 {
	var res int64 = -9999
	if n%m == 0 {
		count := n / m
		for i := 0; i < n; i += count {
			var temp int64
			for j := i; j < i+count; j++ {
				temp += int64(weights[j])
			}
			if temp > res {
				res = temp
			}
		}
	}
	return res
}

/*
*找出最低的测试成本是多少
详细描述
对于一些大型软件项目来说，通常会将任务拆分为很多小模块定义好接口来进行开发。

测试人员对于每个模块都没计了一些回归测试用例，在开发人员提测后需要对每个模块都执行一下相应模块的测试用例

现在各个子模块都完成了开发，假设有一个要求，每次只能合并两个模块的代码，两个模块合并后，需要执行这两个模块的所有测试用例

请你写一个程序帮忙计算一下这样两两合并并测试，测试人员最小需要执行多少次测试用例。

比如一个项目有三个模块，每个模块对应的测试用例数量分别为 [1, 2, 9]

那么先合并前两个模块，需要执行3个测试用例，然后再将合并后的模块与第三个模块合并再测试需要再执行12个测试用例，总计最少需要执行15个测试用例

其他
时间限制: 1000ms

内存限制: 256.0MB

输入输出示例
示例1
输入
[1,2,9]
输出
15
*/
func minEffort(cases []int) int {
	// write code here
	// 两两合并
	c := cases
	var res int
	sort.Ints(c)
	for len(c) > 1 {
		temp := c[0] + c[1]
		// fmt.Println(c, temp)
		res += temp
		c[1] = temp
		c = c[1:]
		// 重新找到合适的位置
		sort.Ints(c)
	}

	return res

}

/*
*最有可能想要输入的命令
详细描述
给你一个非空字符串数组 commands 用来表示可以执行的候选命令列表，和一个用户误输入的（不在 commands 中）命令字符串 input。

求与用户输入的命令的最佳匹配命令。题目保证只有一个最佳匹配。

最佳匹配是指：通过最少的次数对 input  “插入一个字符”或“替换一个字符”或“删除一个字符”使其等于 commands  中的一个。



其他
时间限制: 1000ms

内存限制: 256.0MB

输入输出示例
示例1
输入
["main"],"mian"
输出
"main"
示例2
输入
["server"],"serv"
输出
"server"
示例3
输入
["help","version","status"],"statsu"
输出
"status"
*/
func didYouMean(commands []string, input string) string {
	// write code here
	// 计算重复字母数量
	inputMap := make(map[rune]int)
	for _, b := range input {
		inputMap[b] = inputMap[b] + 1
	}

	comMap := make(map[string]map[rune]int)
	var res string
	var resRatio float64
	for _, c := range commands {
		comMap[c] = make(map[rune]int)
		for _, b := range c {
			comMap[c][b] = comMap[c][b] + 1
		}

		var tempCount int
		for k, v := range inputMap {
			if count, ok := comMap[c][k]; ok {
				if v <= count {
					tempCount += v
				} else {
					tempCount += count
				}
			}
		}

		if (float64(tempCount) / float64(len(c))) > resRatio {
			// 字母重复率
			res = c
			resRatio = float64(tempCount) / float64(len(c))
		}
	}

	return res
}