2.愤怒的奶牛2(angry)
题目描述
贝茜这头奶牛设计了她所认为的下一个热门视频游戏—“愤怒的奶牛”。她认为这是她完全原创的:玩家将一个弹弓射到一个一维的场景中,该场景由位于数字线上各个点的一组干草包组成。每只奶牛都有足够的力量引爆其落地地点附近的干草包,我们的目的是使用一系列奶牛引爆所有的干草包。
有N捆干草包位于这一行的不同整数位置x1,x2,…,xN,如果一头奶牛以能量R着陆在了数轴上的任意一个位置x,那么会引起半径为R(R-x…R+x)的爆炸,并摧毁范围内的所有干草包。
一共有K头奶牛允许被用来作为炮弹,每头奶牛的能量R都相同。请帮忙决定这个最小的能量,使得用这K头奶牛可以摧毁所有的干草包。
输入
第一行包含两个整数N,K(1<=N<=50,000,1<=K<=10)
接下来N行,每行包含一个整数xi,表示每捆干草包的位置(0<=xi<=1,000,000,000)
输出
一行一个整数,表示最少所需要的每头奶牛的能量值R
样例输入
7 2
20
25
18
8
10
3
1
样例输出
5
正解
先快排再二分查找
AC代码
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
long long n,k,l,r,m,x,s,m1,a[50005];
int main()
{
freopen("angry.in","r",stdin);
freopen("angry.out","w",stdout);
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>a[i];
sort(a+1,a+n+1);//快排
m1=1000000000;
l=0;//最小值
r=a[n];//最大值
while(l<r-1)//二分
{
m=(l+r)/2;
x=1;//牛的数量
s=0;
for(int i=1;i<=n-1;i++)
{
s+=a[i+1]-a[i];//两个草垛的距离差
if(s>2*m)//大于半径*2
{
x++;//加一头牛
s=0;//清零
}
}
if(x<=k)r=m;//二分
else l=m;
}
cout<<r;
return 0;
}
下面附本次比赛的其它题目
2020.03.11模拟赛15(第一题)
2020.03.11模拟赛15(第二题)
2020.03.11模拟赛15(第三题)
2020.03.11模拟赛15(第四题)
2020.03.11模拟赛15(总结)