挑战者(0004)
2023-12-21 16:31:39
题意
给定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
?
?
?
?
?
文章来源:https://blog.csdn.net/L3102250566/article/details/135131908
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!