题目描述
现有一个服务器集群(服务器数量为 serverNum),和一批不同类型的任务(用数组 task表示,下标表示任务类型,值为任务数量)。
现需要把这批任务都分配到集群的服务器上,分配规则如下:
- 应业务安全要求,不同类型的任务不能分配到同一台服务器上
- 一种类型的多个任务可以分配在多台服务器上
「负载」定义为某台服务器所分配的任务个数,无任务的服务器负载为0。
「最高负载」定义为所有服务器中负载的最大值。
请你制定分配方案,使得分配后「最高负载」的值最小,并返回该最小值。
解答要求时间限制:1000ms, 内存限制:256MB
输入
第一行一个整数,表示集群中服务器的数量 serverNum,1 ≤ serverNum ≤ 10^9
第二行一个整数,表示这批任务有 taskTypeNum 种类型,1 ≤ taskTypeNum ≤ 100000,且 taskTypeNum <= serverNum
第三行输入 taskTypeNum 个整数,为 task 数组,表示这批任务,1 ≤ task[i] ≤ 10^9
输出
一个整数,表示「最高负载」的最小值
样例
输入样例 1 复制
5 2 7 4
输出样例 1
3
提示样例 1
类型 0 的任务有 7 个,可表示为 0000000;类型 1 的任务有 4 个,可表示为 1111 :
- 按 11、11、00、00、000 或 1、111、00、00、000 分配给 5 台服务器,该分配方案的「最高负载」值为 3,是最小的
- 其它方案的「最高负载」值都更大,例如 11、11、0000、000 的「最高负载」为 4
说明:
任务0和任务1不能分配到同一台服务器上。
一次性制定分配方案,不存在二次分配。
输入样例 2 复制
8 5 101 1 1 20 40
输出样例 2
34
提示样例 2
- 如果「最高负载」为 1,需要的服务器台数为 101 + 1 + 1 + 20 + 40 = 163,超过了给定的服务器数量。因此需要尝试更大的「最高负载」值
… - 如果「最高负载」为 33, 需要的服务器台数为 9
- 如果「最高负载」为 34, 需要的服务器台数为 8
- 如果「最高负载」为 35, 需要的服务器台数也为 8
… - 如果「最高负载」为 40, 需要的服务器台数为 7,服务器有浪费
… - 如果「最高负载」为 101, 需要的服务器台数为 5,服务器有更多浪费
所以「最高负载」值最小为 34
温馨提醒:注意计算中的过程值溢出
提示
温馨提醒:纯暴力解法无法通过所有用例
1.自己的暴力法:50%
/* * Copyright (c) Huawei Technologies Co., Ltd. 2019-2021. All rights reserved. * Description: 上机编程认证 * Note: 缺省代码仅供参考,可自行决定使用、修改或删除 * 只能import Go标准库 */ package main import ( "bufio" "fmt" "io" "os" "strconv" "strings" "math" ) // 待实现函数,在此函数中填入答题代码 func getMinLoad(serverNum int, task []int) int { totalNum := 0 for _, tk := range task { totalNum += tk } minLoad := 1 //fmt.Println(minLoad, totalNum) allNum := 0 if totalNum <= serverNum { return minLoad } for totalNum > serverNum { for _, tk := range task { everySeverNum := int(math.Ceil(float64(tk)/float64(minLoad))) //fmt.Println("===", everySeverNum) allNum += everySeverNum } totalNum = allNum allNum = 0 minLoad++ //fmt.Println("i am here",totalNum, minLoad) } return minLoad-1 } func main() { reader := bufio.NewReader(os.Stdin) serverNum := readInputInt(reader) task := readInputIntArray(reader) result := getMinLoad(serverNum, task) fmt.Println(result) } func readInputInt(reader *bufio.Reader) int { var num int if _, err := fmt.Fscanf(reader, "%d\n", &num); err != nil { fmt.Println(err.Error()) return 0 } return num } func readInputIntArray(reader *bufio.Reader) []int { var num int if _, err := fmt.Fscanf(reader, "%d\n", &num); err != nil { fmt.Println(err.Error()) return nil } if num == 0{ return []int{} } lineBuf, err := reader.ReadString('\n') if err != nil && err != io.EOF { fmt.Println(err.Error()) return nil } lineBuf = strings.TrimRight(lineBuf, "\r\n") lineBuf = strings.TrimSpace(lineBuf) intNums := map2IntArray(lineBuf, " ") if len(intNums) != num{ fmt.Println("int string len is error") return nil } return intNums } func map2IntArray(str string, dem string) []int { tempArray := strings.Split(str, dem) result := make([]int, len(tempArray)) for index, value := range tempArray { value = strings.TrimSpace(value) intVal, err := strconv.Atoi(value) if err == nil { result[index] = intVal } } return result }
2.别人给的二分法: AC
/* * Copyright (c) Huawei Technologies Co., Ltd. 2019-2021. All rights reserved. * Description: 上机编程认证 * Note: 缺省代码仅供参考,可自行决定使用、修改或删除 * 只能import Go标准库 */ package main import ( "bufio" "fmt" "io" "os" "strconv" "strings" ) // 待实现函数,在此函数中填入答题代码 const MAX_TASK_NUM = 100000 /* * 负载对应所需服务器数量 */ func GetServerNum(task []int, taskTypeNum int, load int) int { num := 0 for i := 0; i < taskTypeNum; i++ { num += task[i] / load // 需要完全占满几个服务器 if task[i] % load != 0 { // 少部分溢出任务需单独再占一个服务器 num += 1 } } return num } // 待实现函数,在此函数中填入答题代码 func getMinLoad(serverNum int, task []int) int { taskTypeNum := len(task) taskMax := 0 for i := 0; i < taskTypeNum; i++ { if task[i] > taskMax { taskMax = task[i] } } left := 1 right := taskMax for left <= right { mid := left + (right - left) / 2 // 不使用(l+R)/2是防溢出 if GetServerNum(task, taskTypeNum, mid) <= serverNum { right = mid - 1 // 右区间缩小,服务器有冗余,减少负载 } else { left = mid + 1 // 左区间缩小,服务器不够用,增加负载 } } return left // 最后循环退出时,left的值即为指定服务器数量下的最小负载 } func main() { reader := bufio.NewReader(os.Stdin) serverNum := readInputInt(reader) task := readInputIntArray(reader) result := getMinLoad(serverNum, task) fmt.Println(result) } func readInputInt(reader *bufio.Reader) int { var num int if _, err := fmt.Fscanf(reader, "%d\n", &num); err != nil { fmt.Println(err.Error()) return 0 } return num } func readInputIntArray(reader *bufio.Reader) []int { var num int if _, err := fmt.Fscanf(reader, "%d\n", &num); err != nil { fmt.Println(err.Error()) return nil } if num == 0{ return []int{} } lineBuf, err := reader.ReadString('\n') if err != nil && err != io.EOF { fmt.Println(err.Error()) return nil } lineBuf = strings.TrimRight(lineBuf, "\r\n") lineBuf = strings.TrimSpace(lineBuf) intNums := map2IntArray(lineBuf, " ") if len(intNums) != num{ fmt.Println("int string len is error") return nil } return intNums } func map2IntArray(str string, dem string) []int { tempArray := strings.Split(str, dem) result := make([]int, len(tempArray)) for index, value := range tempArray { value = strings.TrimSpace(value) intVal, err := strconv.Atoi(value) if err == nil { result[index] = intVal } } return result }
感受:
1. 暴力法不行,要想其他思路,二分法还不熟,多练。
2.多审题,没有理解透题目的意思。