分组处理

题目描述:

某项活动有n个单位（编号1到n）参加，需将员工分成若干个小组，每个小组的人数上限为m，小组编号按新建次序从1开始编号。分组时，首先按单位编号次序依次在各单位内部分组，每m人分配到一个新建小组中，不足m人的剩余员工暂不分配；然后按剩余员工人数由大到小的顺序，依次为各单位剩余员工分配小组。

若某单位剩余员工人数为k，则分配方法为：在已建的小组中查找空位数（该小组还可容纳的人数）大于或等于k的小组，如果找到的小组有多个，则选择空位数最少的小组，将此k人分配到该小组中；如果没有找到，则新建一个小组，将此k人分配到该小组中。

设n为5，m为20，各单位员工人数及单位内部的分组过程如第15题左图所示，各单位剩余员工的分组过程如第15题右图所示。

编写程序：给定各单位编号及员工人数，根据上述方法进行分组处理，按单位编号次序输出各单位所分配的分组编号。

请回答下列问题：

（1）由题意可知，若仅将第15题图a中1号单位的员工人数修改为25，然后对图中5个单位重新分组，则1号单位所分配的分组编号为   ▲   。

（2）定义如下bubble_sort(lst)函数，参数lst的每个元素由单位编号和剩余员工人数2个数据项组成。函数的功能是根据每个单位的剩余员工人数，对lst进行降序排序。

输入格式:

第一行两个整数，表示每组的人数m，和n个单位。

接下来n行，每行表示一个单位的编号和总人数。

输出格式:

n行，每行表示各单位所分配的组号。

数据范围:

组数小于100，总人数小于1000。

样例输入:

20 3
1 14
2 7
3 50

样例输出:

单位编号:1，分编号: [3]
单位编号:2，分编号: [4]
单位编号:3，分编号: [1, 2, 4]

提示:

请完善下列程序：

#排序
def bubble_sort(lst):
    n=len(lst)
    for i in range(0, n-1):
        for j in range(n-1, i, -1):
            if ___________________: #填空1
                tmp=lst[j]
                lst[j]=lst[j-1]
                lst[j-1]=tmp
        if lst[i][1]==0:
            break
    return

def group(data, m):      
    n=len(data)
    a=[]
    for i in range(n+1):  
        a.append([]) # a[i]初始化为空列表，存放编号为i的单位所分配的分组编号
    gnum=0
    for i in range(n):       #各单位内部分组
        while data[i][1]>=m:
            gnum+=1
            k=data[i][0]
            a[k].append(gnum)
            ______________     #填空2   
    bubble_sort(data)       #根据每个单位的剩余员工人数，对data进行降序排序
    b=[]
    for i in range(m):
        b.append([])
    i=0  
    while i<n and data[i][1]!=0:   #对剩余员工分组
        ______________      #填空3
        while j<m and len(b[j])==0: 
            ______________    #填空4
        if j<m:         
            v=b[j].pop()                    
        else:
            gnum+=1   
            v=gnum
        a[data[i][0]].append(v)            
        ____________         #填空5
        i += 1
    #输出各单位的分组编号，代码略
    for i in range(n):
        print("单位编号:"+str(i+1)+"，分编号:",a[i+1])
   
'''
读取小组人数上限存入m；读取1至n号单位的数据，依次存入列表data的data[0]至data[n-1]中。
data[i]包含2个数据项，data[i][0],data[i][1]分别存放单位编号及员工人数，代码略
'''
m ,n = map( int, input().split() )
data = []
for i in range( n ):
    x, y = map( int,  input().split() )
    data.append( [x,y] )
group(data, m)

时间限制: 1000ms
空间限制: 256MB

---

来源: 2024.01 选考真题T15