20746: 满足合法工时的最少人数

http://cs101.openjudge.cn/practice/20746/

若干个工作任务，需要在一天内完成。给一个正整数数列，存储每个任务所需的工时。

国家法律规定，员工的日工作时长不能超过t。

公司决定雇佣k个员工，每个任务都会让所有员工一同分担，于是每个任务执行的时间等于它所需的工时除以k。

所有任务执行的时间累加起来得到s。

为了满足合法工作不加班，请在s<=t的前提下，找出所需的最少员工数量k。

分担说明:每个任务分担后的时间都是小数点无条件进位取整

7个工时/3个员工 = 3小时, 10个工时/2个员工=5小时

必定存在结果(不用考虑t<数列长度的状况)

输入

一个逗号分隔的数列一个正整数

输出

一个正整数

样例输入

1,2,5,9
5

样例输出

提示

如果员工数是4，sum(1+1+2+3)=7 如果员工数是5，sum(1+1+1+2)=5 如果员工数是6，sum(1+1+1+2)=5 所以答案是5

use a binary search approach. The minimum number of employees can be 1 and the maximum can be the maximum work hours in the tasks. For each mid value in the binary search, calculate the total work hours and compare it with the legal work hours. If it's more, increase the number of employees, else decrease it.

python

def min_employees(tasks, t):
    left, right = 1, max(tasks)
    while left < right:
        mid = (left + right) // 2
        total_hours = sum((task + mid - 1) // mid for task in tasks)
        if total_hours > t:
            left = mid + 1
        else:
            right = mid
    return left

# 读取输入并处理
tasks = list(map(int, input().split(',')))
t = int(input())
print(min_employees(tasks, t))

20746: 满足合法工时的最少人数 ​

20746: 满足合法工时的最少人数