目录
模板：
题目一（分巧克力）：
代码：
题目二（M次方根）：
编辑代码：
题目三（跳石头）：
代码：
题目四（扫地机器人）：
代码：
模板：
while (low < high)//在递增序列中查找>=x的数中最小的一个
{
int mid = (low + high) / 2;
if (a[mid] >= x)
high = mid;
else
low = mid + 1;
}
while (low < high)//在递增序列中查找<=x的数中最大的一个
{
int mid = (low + high) / 2;
if (a[mid] <= x)
low = mid;
else
high = mid - 1;
}题目一（分巧克力）：
代码：
#include<iostream>
using namespace std;
int n,k,h[100010],w[100010];
bool pd(int l)//分l边长的巧克力是否满足
{
int sum=0;
for(int i=1;i<=n;i++)//判断可以分几块
{
sum+=(h[i]/l)*(w[i]/l);
if(sum>=k)//满足分大于等于k个人，返回true
return true;
}
return false;
}
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>h[i]>>w[i];
int high=0;
for(int i=1;i<=n;i++)//查找二分上界
{
high=max(high,h[i]);
high=max(high,w[i]);
}
int low=1,mid=0;
while(low<high)//二分查找
{
mid=(low+high+1)/2;
if(pd(mid))
low=mid;
else
high=mid-1;
}
cout<<low;
}题目二（M次方根）：
代码：
#include<iostream>
#include<iomanip>
using namespace std;
double n,m,l,r,mid;
double eps=1e-8;//因为计算保留七位小数，则每次加10负8次方
bool pd(double a,double d)
{
double c=1;
while(d>0)//c的d次方
{
c*=a;
d--;
}
if(c>=n)
return true;
else
return false;
}
int main()
{
cin>>n>>m;
l=0,r=n;
while(l+eps<r)//二分查找
{
mid=(l+r)/2;
if(pd(mid,m))
r=mid;
else
l=mid;
}
cout<<fixed<<setprecision(7)<<l<<endl;//输出七位小数
}题目三（跳石头）：
代码：
#include <iostream>
using namespace std;
int l, n, m, mid;
int stone[500010];
bool check(int d)//判断距离d是否合适
{
int num = 0, pos = 0;//num记录搬走的石头，pos当前站立的石头
for (int i = 1; i <= n; i++)
{
if (stone[i] - pos < d)//第i块石头需要搬走
num++;//搬走石头数加一
else
pos = stone[i];//否则，位置站到该位置
}
if (num <= m)
return true;
else
return false;
}
int main()
{
cin >> l >> n >> m;
for (int i = 1; i <= n; i++)
cin >> stone[i];
int low = 0, high = l, ans;
while (low < high)//二分查找
{
mid = (low + high + 1) / 2;
if (check(mid))
{
low = mid;
ans = mid;
}
else
high = mid - 1;
}
cout << ans;
}题目四（扫地机器人）：
代码：
#include<iostream>
#include<algorithm>
using namespace std;
int pos[1000010];
int n, k,mid;
bool check(int len)//每个机器扫len个区域
{
int tmp = 0;//表示扫到的位置
for (int i = 1; i <= k; i++)
{
if (pos[i] - len <= tmp)//如果当前机器人扫它的左边是比其它机器人省时间的，所以如果能够清扫完左边还没扫的，说明方案有可能可行
{
if (pos[i] <= tmp)//如果当前机器人已经处于扫过的位置，则机器人只扫右侧区域
tmp = pos[i] + len - 1;
else//否则从上一次扫到的位置开始扫
tmp += len;
}
else
return 0;//方案不可行
}
return tmp >= n;//全部扫完，方案可行
}
int main()
{
cin >> n >> k;
for (int i = 1; i <= k; i++)
cin >> pos[i];
sort(pos + 1, pos + k + 1);//机器人位置从小到大排序
int l = 0, r = n, ans;
while (l <= r)//二分查找，每个机器人扫的距离，最小0，最大n
{
mid = (l + r) / 2;
if (check(mid))
{
r = mid - 1;
ans = mid;//记录最小的答案
}
else
l = mid + 1;
}
cout << (ans - 1) * 2 << endl;//时间来回乘2
}
