挑战者（0004）

题意

给定n把锁，要求在时间m内全部打开，给定每一把锁打开需要的尝试的次数，要求能在规定时间内打开的最小速度，时间用小时来计算，不足一个小时按照一个小时计算，比如说，需要6次尝试打开一把锁，速度是4次每小时，那么打开这把锁需要两个小时，一个小时之内只能处理一把锁

输入

4 8

3 6 7 11

输出

4

说明

第一把锁用时1小时，第二把锁用时2小时，第三把锁用时2小时，第四把锁用时3小时，总共8小时

代码

#include<bits/stdc++.h>
using namespace std;

const int N=1e4+10;
int a[N];

bool check(int num,int n,int m)
{
	int cnt=0;
	for(int i=0;i<n;i++)
	{
		if(a[i]%num==0)	cnt+=a[i]/num;
		else	cnt+=a[i]/num+1;
	}
	
	return cnt<=m;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int n,m;
	cin>>n>>m;
	for(int i=0;i<n;i++)	cin>>a[i];
	
	int l=0,r=1e9+10,ans=0;
	while(l<r)
	{
		int mid=(l+r)/2;
		if(check(mid,n,m))	r=mid;
		else	l=mid+1;
	}
	
	ans=l;
	cout<<ans<<endl;
	
	return 0;
}

总结

1.二分查找

二分查找需要注意的就是，如果我们更新的是左边界，

l=mid;

那么为了防止死循环，要写成这样

mid=(l+r+1)/2;

假设没有加一，

//假设l=r-1
mid=(l+r)/2=(r-1+r)/2=r-1;
l=mid=r-1;
//也就是说更新之后边界的数值没有发生改变，没有发生改变就会导致死循环

加一之后

//还是假设l=r-1
mid=(l+r+1)/2=(r-1+r+1)/2=r;
l=mid=r;
//完成了边界的更新，不会发生死循环

当然，这里没有用到这个，因为需要更新的是右边界，我们需要寻找的是最小的速度，也就是说寻找的答案越靠近0越好，如果满足条件我们就更新右边界

2.设计check函数

判断二分的结果是否符合题目的要求，枚举每一把锁，可以需要尝试的次数可以整除二分结果就累加求和，不能整除就向上取整，向上取整是直接在原来的基础上加一，因为整数运算默认向下取整

bool 函数，最后一行有讲究

	return cnt<=m;
//cnt表示的是我们累加求和的结果，m表示的是规定时间
//如果能在规定时间内解锁，就满足不等式，返回true
//否则返回false

?

?

?

?

?