愤怒的DZY（二分）

愤怒的DZY
【问题描述】
“愤怒的小鸟”如今已经是家喻户晓的游戏了，机智的WJC最近发明了一个类似的新游戏：“愤怒的DZY”。游戏是这样的：玩家有K个DZY，和N个位于不同的整数位置：X1，X2，…，XN的干草包。每一个DZY都可以站在某个位置：X 扔炸弹，扔完炸弹，这个DZY就会挂掉。扔炸弹的半径为R（且每次每个DZY扔炸弹的半径不变，都是R，而站的位置X可以改变）,破坏范围为的X−R~X+R（即位置在X-R到X+R（含X-R,X+R）都会被炸掉）。现在给定DZY的个数K，和干草堆的位置：X1，X2，…，XN，问你最小的可以炸掉所有干草堆的半径R。
【输入说明】
第一行两个正整数N,K。接下来N行，每行一个数，依次是：X1，X2，…，XN。
【输出说明】
仅一行，代表最小的可以炸掉所有干草堆的半径R。
【样例输入】
7 2
20
25
18
8
10
3
1
【样例输出】
5

题解：一看就是二分；对于R，可以从第一个数开始当区间大于2*R就加一个炮台；根据炮台二分找R

代码：

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

const int INF=0x3f3f3f3f;

#define SI(x) scanf("%d",&x)

#define SL(x) scanf("%lld",&x)

#define PI(x) printf("%d",x)

#define PL(x) printf("%lld",x)

#define mem(x,y) memset(x,y,sizeof(x))

#define P_ printf(" ")

typedef long long LL;

const int MAXN=100010;

int m[MAXN];

int N,K;

bool wk(int r){

	int s,cnt=1;

	s=m[0];

	for(int i=1;i<N;i++){

		if(m[i]-s>2*r)s=m[i],cnt++;

	}

	if(cnt>K)return true;

	else return false;

}

int erfen(int l,int r){

	int mid;

	while(l<=r){

		mid=(l+r)/2;

		if(wk(mid))l=mid+1;

		else r=mid-1;

	}

	return l;

}

int main(){

	while(~scanf("%d%d",&N,&K)){

		for(int i=0;i<N;i++){

			SI(m[i]);

		}

		sort(m,m+N);

		printf("%d\n",erfen(0,100010));

	}

	return 0;

}

巴特西

愤怒的DZY（二分）

最新文章

热门文章