[已解决]Python：每日一题 300

zltzlt

今天的题目：

给定 len(pages) 本书，每本书的页数都存储在 pages 里。
现在有 k 个人来复印这些书籍，而每个人只能复印编号连续的一段的书，比如一个人可以复印 pages[0]、pages[1]、pages[2]，但是不可以只复印 pages[0]、pages[2]、pages[3] 而不复印 pages[1]。

所有人复印的速度是一样的，复印一页需要花费一分钟，并且所有人同时开始复印。
合理分配这 k 个人的任务，使得这 len(page) 本书能够被尽快复印完。返回完成复印任务最少需要的分钟数。

示例 1：

输入：pages = [3, 2, 4]，k = 2
输出：5
解释：第一个人复印前两本书。耗时 5 分钟；第二个人复印第三本书，耗时 4 分钟。

示例 2：

输入：pages = [3, 2, 4]，k = 3
输出：4
解释：三个人各复印一本书。

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

Stubborn

2020-1-5 12:38:29

1. from typing import List
   
2. def book_copy(pages:List[int], k:int) -> int:
   
3.     """
   
4.     算法->贪婪+二进制搜索
   
5.     **思考如果给定N本书，我们限定时间不超过T，需要多少复印员？**
   
6.     题目规定同一本书只能有一个人复印，并且是连续复印。
   
7.     所以我们让第一个人复印，一直到复印的时间超过T的时候，某本书(假设为pages[i])还没有复印，我们再让第二个人复印，
   
8.         直到复印超时，或者复印完毕。
   
9.     我们所需要的人数，即是最少的复印员。
   
10. 
    
11.     现在我们就可以试不同的T，看所需最少抄写员是不是超过了k。
    
12.     从两个方向看：
    
13.         A: 假设T等于1个人复印完所有数的时间，需要最少的复印员就是 1 ，如果 1 < k ,说明时间需要减少。
    
14.         B: 假设T是`最厚`的那本书由一个人复印完锁需要的时间，需要最少的复印员就是N。如果 N > K,说明时间需要增加。
    
15.     这个思路告诉我们可以用Binary Search来解决这个问题。
    
16.         A、B分别给出了T的取值区间。如果给定T所需人数<k，则T要变小，如果所需人数>k, 则T要变大。
    
17.             若所需人数=k, 说明此T可以，但还可以试试能不能把T变小
    
18. 
    
19.     check()就是判断N本书，<=T时间, k个人能不能搞定。
    
20. 
    
21.     注意，这是一个典型的最大值最小化问题。通常这类问题要先考虑用二进制搜索(Binary Search)。
    
22. 
    
23.     代码如下：
    
24.     """
    
25.     if not len(pages):retrun 0
    
26.     def check(pages:List[int], limit:int, k:int) ->bool:
    
27.         Count,Sum = 1, 0
    
28.         length_v = len(pages)
    
29.         for i in range(length_v):
    
30.             if pages[i] > limit: return False
    
31.             if pages[i] + Sum > limit:
    
32.                 Count,Sum = Count + 1 , pages[i]
    
33.             else:Sum += pages[i]
    
34.         return Count <= k
    
35. 
    
36.     left, right = max(pages), sum(pages)
    
37. 
    
38.     while left + 1 < right:
    
39.         mid = left + (right - left) // 2
    
40.         if check(pages, mid, k):
    
41.             right = mid
    
42.         else: left = mid
    
43. 
    
44.     if check(pages, left, k):return left
    
45.     return right

复制代码

跳转到最佳答案楼层

Stubborn

1. from typing import List
   
2. def book_copy(pages:List[int], k:int) -> int:
   
3.     """
   
4.     算法->贪婪+二进制搜索
   
5.     **思考如果给定N本书，我们限定时间不超过T，需要多少复印员？**
   
6.     题目规定同一本书只能有一个人复印，并且是连续复印。
   
7.     所以我们让第一个人复印，一直到复印的时间超过T的时候，某本书(假设为pages[i])还没有复印，我们再让第二个人复印，
   
8.         直到复印超时，或者复印完毕。
   
9.     我们所需要的人数，即是最少的复印员。
   
10. 
    
11.     现在我们就可以试不同的T，看所需最少抄写员是不是超过了k。
    
12.     从两个方向看：
    
13.         A: 假设T等于1个人复印完所有数的时间，需要最少的复印员就是 1 ，如果 1 < k ,说明时间需要减少。
    
14.         B: 假设T是`最厚`的那本书由一个人复印完锁需要的时间，需要最少的复印员就是N。如果 N > K,说明时间需要增加。
    
15.     这个思路告诉我们可以用Binary Search来解决这个问题。
    
16.         A、B分别给出了T的取值区间。如果给定T所需人数<k，则T要变小，如果所需人数>k, 则T要变大。
    
17.             若所需人数=k, 说明此T可以，但还可以试试能不能把T变小
    
18. 
    
19.     check()就是判断N本书，<=T时间, k个人能不能搞定。
    
20. 
    
21.     注意，这是一个典型的最大值最小化问题。通常这类问题要先考虑用二进制搜索(Binary Search)。
    
22. 
    
23.     代码如下：
    
24.     """
    
25.     if not len(pages):retrun 0
    
26.     def check(pages:List[int], limit:int, k:int) ->bool:
    
27.         Count,Sum = 1, 0
    
28.         length_v = len(pages)
    
29.         for i in range(length_v):
    
30.             if pages[i] > limit: return False
    
31.             if pages[i] + Sum > limit:
    
32.                 Count,Sum = Count + 1 , pages[i]
    
33.             else:Sum += pages[i]
    
34.         return Count <= k
    
35. 
    
36.     left, right = max(pages), sum(pages)
    
37. 
    
38.     while left + 1 < right:
    
39.         mid = left + (right - left) // 2
    
40.         if check(pages, mid, k):
    
41.             right = mid
    
42.         else: left = mid
    
43. 
    
44.     if check(pages, left, k):return left
    
45.     return right

复制代码

TJBEST

版主，我又来了，这次代码依然较长而且可能超时

1. def fun300(pages,k):
   
2.     '''回溯法求解'''
   
3.     def calMaxstep(eachChoose):
   
4.         maxPage = 0
   
5.         for eachPerson in eachChoose:
   
6.             PersonPages = sum(eachPerson)
   
7.             if maxPage < PersonPages:
   
8.                 maxPage = PersonPages
   
9.         return maxPage
   
10.     def findAll(pages,start,var_num,temp,all_list):#pages页数大纲，start起始位置,var_num第几个人，temp回溯法，all_list遍历最大值
    
11.         if var_num == 1:
    
12.             temp.append(pages[start:len(pages)])
    
13.             mintemp = calMaxstep(temp)
    
14.             if mintemp < all_list[len(all_list) - 1]:
    
15.                 all_list.append(mintemp)
    
16.             temp.pop()
    
17.         else:
    
18.             for pro in range(0,len(pages)-var_num + 1 - start):
    
19.                 if sum(pages[start:(start + pro + 1)]) < all_list[len(all_list) -1]:
    
20.                     temp.append(pages[start:(start + pro + 1)])
    
21.                     findAll(pages,start + pro + 1,var_num - 1,temp,all_list)
    
22.                     temp.pop()
    
23.                 else:
    
24.                     break
    
25.     m = len(pages)#书的个数
    
26.     if m <= k:
    
27.         return max(pages) if pages!=[] else 0
    
28.     else:
    
29.         all_list = [sum(pages)]#记录遍历的（各个组合最大值）的最小值
    
30.         temp = []#回溯法中间变量
    
31.         findAll(pages,0,k,temp,all_list)
    
32.     return all_list[len(all_list) - 1]   
    

复制代码

塔利班

1. def f300(pages,k):
   
2.     l=len(pages)
   
3.     if k>=l:
   
4.         return max(pages)
   
5.     elif k==1:
   
6.         return sum(pages)
   
7.     else:
   
8.         t=sum(pages)//k
   
9.         tlist=[[] for _ in range(k)]
   
10.         i=0
    
11.         c=[]
    
12.         for e in pages:
    
13.             s=sum(tlist[i])
    
14.             if e>2*(t-s) and i<l-1:
    
15.                 i+=1
    
16.                 c.append(s)
    
17.             tlist[i].append(e)
    
18.         c.append(sum(tlist[-1]))
    
19.         return max(c)

复制代码

Croper

先写一个，
有很多能优化的地方，

1. def func_300(page,n):
   
2.     """
   
3.     300期留名
   
4.     """
   
5.     if (len(page)==0):
   
6.         return 0
   
7.     all=sum(page)
   
8.     while (len(page)>n):
   
9.         t,k=0,all
   
10.         for i in range(len(page)-1):
    
11.             if page[i]+page[i+1]<k:
    
12.                 k=page[i]+page[i+1]
    
13.                 t=i
    
14.         page.pop(t)
    
15.         page[t]=k
    
16.     return max(page)
    

复制代码

zltzlt

塔利班 发表于 2020-1-5 13:26

输入 pages = [], k = 1 报错

zltzlt

Croper 发表于 2020-1-5 13:33
先写一个，
有很多能优化的地方，

解答错误

输入：pages = [1,9,7,3,4,7], k = 3
输出：14
预期结果：11

kinkon

1. def f300(pages:list,k:int):
   
2.     pages_rev = pages[::-1]
   
3.     if not pages or k < 1:return 0
   
4.     elif k == 1:return sum(pages)
   
5.     elif k >= len(pages):return max(pages)
   
6.     #elif sum(pages)/k <= max(pages):return max(pages)
   
7.     else:  
   
8.         num, res= 0, []      
   
9.         for i in range(len(pages)):            
   
10.             num += pages[i]              
    
11.             if num >= sum(pages)/k:               
    
12.                 res.append(num)               
    
13.                 num = 0
    
14.         for j in range(len(pages_rev)):            
    
15.             num += pages_rev[j]              
    
16.             if num >= sum(pages)/k:               
    
17.                 res.append(num)               
    
18.                 num = 0      
    
19.         #print(res)   
    
20.         return min(res)

复制代码

zltzlt

kinkon 发表于 2020-1-5 15:22
手机码字，也不知道有没缩进错误和码错代码
def f300(pages:list,k:int):
    ln=range(pages)

出错：TypeError: 'list' object cannot be interpreted as an integer

kinkon

zltzlt 发表于 2020-1-5 15:25
出错：TypeError: 'list' object cannot be interpreted as an integer

电脑测试几个实例都没问题，可能是手机码代码出错，换了电脑密码忘记了，悲哀

Croper

zltzlt 发表于 2020-1-5 13:57
解答错误

输入：pages = [1,9,7,3,4,7], k = 3

...好吧，思路方向错了。。。
重新写了个动态规划的。。总感觉会很慢啊。。。

1. def func_300(page,n):
   
2.     """
   
3.     300期留名
   
4.     """
   
5.     buffer={}
   
6.     def dp(k,n):
   
7.         if (k,n) in buffer:
   
8.             return buffer[(k,n)]
   
9.         i=1
   
10.         ret=sum(page[:k])
    
11.         if (n>1):
    
12.             while k-i>=0:
    
13.                 a=dp(k-i,n-1)
    
14.                 b=sum(page[k-i:k])
    
15.                 ret=min(ret,max(a,b))
    
16.                 if (b>=a):
    
17.                     break
    
18.                 i+=1
    
19.         buffer[(k,n)]=ret
    
20.         return ret
    
21. 
    
22.     return dp(len(page),n)
    

复制代码

塔利班

1. def f300(pages,k):
   
2.     if not pages:
   
3.         return 0
   
4.     l=len(pages)
   
5.     if k>=l:
   
6.         return max(pages)
   
7.     elif k==1:
   
8.         return sum(pages)
   
9.     else:
   
10.         t=sum(pages)//k
    
11.         tlist=[[] for _ in range(k)]
    
12.         i=0
    
13.         c=[]
    
14.         for e in pages:
    
15.             s=sum(tlist[i])
    
16.             if e>2*(t-s) and i<l-1:
    
17.                 i+=1
    
18.                 c.append(s)
    
19.             tlist[i].append(e)
    
20.         c.append(sum(tlist[-1]))
    
21.         return max(c)
    

复制代码

好吧，= =，没页数也算个书

zltzlt

塔利班 发表于 2020-1-5 15:54
好吧，= =，没页数也算个书

只是一道题

kinkon

终于登陆进来了，麻烦再测试下

1. def f300(pages:list,k:int):   
   
2.     if not pages or k < 1:return 0
   
3.     elif k == 1:return sum(pages)
   
4.     elif k >= len(pages):return max(pages)   
   
5.     else:
   
6.         if sum(pages)%k == 0:
   
7.             return sum(pages)//k
   
8.         else:
   
9.             return sum(pages)//k + 1
   
10. 
    
11. if __name__ == '__main__':
    
12.     print("示例1，输入：pages=[3, 2, 4]，k=2，输出： ",f300([3, 2, 4], 2))
    
13.     print("示例2，输入：pages=[3, 2, 4]，k=3，输出： ",f300([3, 2, 4], 3))
    
14.     print("示例3，输入：pages = [], k = 1，输出： ",f300([], 1))
    
15.     print("示例3，输入：pages = [1,9,7,3,4,7], k = 3，输出： ",f300([1,9,7,3,4,7],3))
    
16.    
    

复制代码

Unicorn#

300期啦~ 撒花&#10047;&#10047;ヽ(°▽°)ノ&#10047;

大家千万不要用[[0]*m]*n的方式创建二维列表，不要问我是怎么知道的

1. # -*- coding: utf-8 -*-
   
2. def solve(pages, k):
   
3.     INF = 0Xffff
   
4.     n = len(pages)
   
5.     record = [[(0, 0)for j in range(k+1)]for i in range(n+1)]      #(final time, last person time)
   
6.     for i in range(1, n+1):
   
7.         for j in range(1, k+1):
   
8.             record[i][j] = min(
   
9.                     (max(record[i-1][j-1][0], pages[i-1]), pages[i-1]) if j > 1 or i == 1 else (INF, pages[i-1]),
   
10.                     (max(record[i-1][j][0], record[i-1][j][1]+pages[i-1]), record[i-1][j][1]+pages[i-1]),
    
11.                     (record[i][j-1][0], 0) if j > 1 else (INF, 0)
    
12.                     )
    
13.     return record[n][k][0]

复制代码

zltzlt

塔利班 发表于 2020-1-5 15:54
好吧，= =，没页数也算个书

输入 pages = [1, 1, 1, 1], k = 3 出错

zltzlt

kinkon 发表于 2020-1-5 15:55
终于登陆进来了，麻烦再测试下

解答错误

输入：[13,999,1,2,3,9,11], k = 2
输出：519
预期结果：1012

zltzlt

Unicorn# 发表于 2020-1-5 16:01
300期啦~ 撒花&#10047;&#10047;ヽ(°▽°)ノ&#10047;

大家千万不要用[[0]*m]*n的方式创建二维列表，不要 ...

解答错误

输入：[13,999,1,2,3,9,11], k = 2
输出：1025
预期结果：1012

zltzlt

Croper 发表于 2020-1-5 15:45
...好吧，思路方向错了。。。
重新写了个动态规划的。。总感觉会很慢啊。。。

确实有点慢，不过侥幸通过了5042 ms

Unicorn#

zltzlt 发表于 2020-1-5 16:06
解答错误

输入：[13,999,1,2,3,9,11], k = 2

这个有后效性就很烦
再想想