P6174题解
cyrxdzj
·
·
题解
一、思路
首先，R 越大，干草就越有可能被引爆完。
显然，这需要使用二分算法。
二分算法的精髓在于 `check` 函数，用于检查这个答案是否符合题意。那么，这道题的 `check` 应该怎么做呢？
### 二、检查函数
首先，干草堆的位置必须有序。这不难，一个 `sort` 函数下来就搞定，数据范围也不大。
我们可以定义一个变量 `position`，代表当前已被发射的奶牛，最远可以炸到那个点上。初始值为 `-0x7fffffff`，这是 `int` 型的最小值。
然后，顺序遍历所有干草堆。如果 `position` 加上当前假设的距离小于这个干草堆的位置，就说明这个干草堆还没被炸到，因此要再多一个奶牛，并将 `position` 更新为当前干草堆的位置加上当前假设的距离。
如果使用的奶牛数量大于 $K$，就说明这个距离太小，返回 `false`。
到了最后，如果使用的奶牛数量不大于 $K$，就说明这个距离足够了，返回 `true`。
### 三、坑点
记得排序！
### 四、完整代码
```cpp
#include<cstdio>
#include<algorithm>
using namespace std;
int n,k;
int grass[50005];
int left,right=1000000000;
int middle;
int ans;
bool check(int x)//检查函数。
{
int use_cow=0,position=-0x7fffffff;
for(int i=1;i<=n;i++)
{
if(position+x<grass[i])
{
use_cow++;
position=grass[i]+x;
if(use_cow>k)
{
return false;
}
}
}
return true;
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
{
scanf("%d",&grass[i]);
}
sort(grass+1,grass+1+n);//记得排序！
while(left<=right)//二分。
{
middle=(left+right)>>1;
if(check(middle))
{
right=middle-1;
ans=middle;
}
else
{
left=middle+1;
}
}
printf("%d\n",ans);
return 0;//完结撒花！
}
```
By [dengzijun](https://www.luogu.com.cn/user/387836)