蓝桥试题 算法提高 打包（二分法，最大值最小化）

蓝桥试题 算法提高 打包（二分法，最大值最小化）

资源限制

时间限制：1.0s   内存限制：256.0MB

问题描述

　　Lazy有N个礼物需要打成M个包裹，邮寄给M个人，这些礼物虽然很便宜，但是很重。Lazy希望每个人得到的礼物的编号都是连续的。为了避免支付高昂的超重费，他还希望让包裹的最大重量最小。

输入格式

　　一行两个整数N和M。
　　一行N个整数，表示N个礼物的重量。

输出格式

　　一个整数，表示最小的最大重量。

样例输入

3 2
1 1 2

样例输出

2

数据规模和约定

　　N, M <= 100,000
　　重量 <= 1,000

分析：

结果必定落在【max（nums）， sum（nums）】这个区间内，因为左端点对应每个单独的元素构成一个子数组，右端点对应所有元素构成一个子数组。

然后可以利用二分查找法逐步缩小区间范围，当区间长度为1时，即找到了最终答案。

# 开发人：HGC
# 开发时间：2021-11-16 20:20

n,m=list(map(int,input().split()))
weight=list(map(int,input().split()))
right=sum(weight)
left=max(weight)
while right>left:
    mid=int((left+right)/2)
    temp=0
    count=1
    for i in weight:
        temp+=i
        if temp>mid:
            temp=i
            count+=1
    if count>m:
        left=mid+1
    else:
        right=mid
print(left)

另外有一个题，和这个非常相似，但是不知哪里出了问题，只对了40%

试题 算法提高 和谐宿舍

资源限制

时间限制：1.0s   内存限制：256.0MB

问题描述

　　我的某室友学过素描，墙上有n张他的作品。这些作品都是宽度为1，高度不定的矩形，从左到右排成一排，且底边在同一水平线上。
　　宿舍评比就要来了，为了及格，我们决定买不多于m块的矩形木板，把这些作品和谐掉。要求木板也从左到右排成一排，且底边与作品的底边在同一水平线上。
　　在能够把所有作品和谐掉的前提下，我们希望最大的那块木板的面积最小，问最大木板的面积。

 

 

输入格式

　　第一行两个数n和m，表示作品数和木板数；
　　第二行n个数Hi，表示从左到右第i个作品的高度。

输出格式

　　一行一个数ans，表示答案。

样例输入

5 2
4 2 3 5 4

样例输出

12

数据规模和约定

　　对于30%的数据：1<=n，m<=10；
　　对于100%的数据：1<=n，m<=100000，1<=Hi<=10000。

# 开发人：HGC
# 开发时间：2021-11-17 14:01

n,m=list(map(int,input().split()))
height=list(map(int,input().split()))
right=max(height)*n
left=max(height)
while lefthigh:
            high=height[i]
        temp+=1
        if temp*high>mid:
            #print('分割点是',i)
            temp=1
            high=0
            count+=1
    #print('count',count)
    if count>m:
        left=mid+1
    else:
        right=mid
print(left)