小慕正在设计一个基于时分复用的灵活带宽分配系统。在该系统中,物理带宽被按时间划分为多个,每个时隙对应固定的带宽。每个客户可以申请占用一定数量的时隙,从而实现带宽的灵活分配。时隙分为两种粒度:5G时隙(称为)和1G时隙(称为)。客户业务的带宽需求必须是时隙粒度的整数倍。例如,一个50GE的物理端口可以按5G粒度划分为10个主时隙,这些主时隙可以分配给多个客户,每个客户根据需求占用多个时隙。 限制一:1G子时隙不能跨5G主时隙分配。 举例1:客户业务带宽需求为2G,分配“0[0,1]”或“0[1,4]”是合法的,而分配“0[0],1[0]”是非法的。 说明:我们使用`x0,x1[y0,y1,...]`表示时隙位置信息,`x`表示主时隙编号(从0开始),`y`表示子时隙编号(0~4)。`x1[y1,y2]`表示`x1`主时隙下的`y1`和`y2`两个子时隙,占用的带宽为2G。 限制二:如果客户需求的带宽大于等于5G,则只能分配5G的整数倍带宽。 举例2:客户业务带宽需求为6G,分配“0,1”或“1,9”是合法的,而分配“0,1[0]”是非法的。 限制三:同一个时隙只能被一个客户业务占用。 小慕需要实现一种时隙分配算法,为给定的客户业务带宽需求分配时隙,使得未成功分配时隙的客户业务带宽之和最小。
提示:带虚线的词点一下有通俗解释。
时间限制 1000 ms · 内存限制 128 MB