[Usaco2016 Jan]Angry Cows

Description

奶牛Bessie设计了一个游戏：“愤怒的奶牛”。游戏的原型是：有一些可爆炸的草堆分布在一条数轴的某些坐标上
，玩家用弹弓把一头奶牛发射到数轴上。奶牛砸到数轴上的冲击波会引发附近的草堆爆炸。游戏的目标是玩家用一些奶牛炸掉所有的草堆。有N个草堆在数轴的不同位置，坐标为x1,x2,….,xn。如果玩家以能量R把奶牛发射到坐标x，就会引爆半径R及以内的的草堆，即坐标范围[x-R,x+R]的草堆都会燃爆。现在有K头奶牛，每头奶牛的能量都是
R，请计算如果要引爆所有的草堆，最小的R是多少？

Input

第一行：2个整数N(1≤N≤50,000)和K(1≤K≤10)。 
下面有N行,每行一个整数：x1,x2,…,xn，范围在[0…1,000,000,000]。 

Output

输出最小可能的R。

Sample Input

7 2
20
25
18
8
10
3
1

Sample Output

5

思路

二分

二分答案R，按升序循环坐标，若该坐标大于t，则需要一头新的奶牛，为了使引爆的炸弹尽量多，所以使现在所在的点为最左边的点d[i],中间的引爆点为d[i]+mid+1,最右边的点为d[i]+mid+1+mid,即t=d[i]+mid+1+mid;否则就说明该坐标上的炸弹已经被引爆了。每次所用的奶牛数若大于限定的奶牛数，则check失败；反之check成功。最后ans取min。

代码

#include<bits/stdc++.h>
using namespace std;
int n,cow,d[50001],a1=1,a2,mid,used,t,ans=2147483647;
bool check()
{
	used=0;//使用的奶牛 
	t=0;//坐标为1—t内的所有坐标的炸弹已经引爆了 
	for(int i=1;i<=n;i++)
		if(t<=d[i])//该坐标的炸弹未被引爆 
		{
			used++;//使用的奶牛数量+1 
			if(used>cow)//使用的奶牛数超过限制，则check失败 
				return false; 
			t=d[i]+mid+mid+1;//奶牛引爆d[i]——d[i]+mid+1——d[i]+mid+1+mid 
		}
	return true;//check成功 
}
int main()
{
	scanf("%d %d",&n,&cow);
	for(int i=1;i<=n;i++)
		scanf("%d",&d[i]);
	sort(d+1,d+1+n);//升序排列		
	a2=d[n]-d[1]+1;
	while(a1<=a2)
	{
		mid=(a1+a2)/2;
		if(check())//check成功 
		{
			ans=min(ans,mid); 
			a2=mid-1; 
		} 
		else//check失败 
			a1=mid+1;
	}
	printf("%d",ans);//输出答案 
	return 0;
} 

最后

以上就是纯真香氛为你收集整理的[Usaco2016 Jan]Angry Cows[Usaco2016 Jan]Angry Cows的全部内容，希望文章能够帮你解决[Usaco2016 Jan]Angry Cows[Usaco2016 Jan]Angry Cows所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。