贪心算法——疯狂的牛牛

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了贪心算法——疯狂的牛牛，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含780字，纯文字阅读大概需要2分钟。

内容图文

/*
	疯狂的牛牛
	n个隔间  c头牛
	使每两头牛之间的最小距离最大化 
	思路：
	转化为判定性问题
	判断间距d是否可行；对间距d采取二分策略 
*/ 

#include<stdio.h>
#include<algorithm>
using namespace std;

const int MAXN = 1e5 + 10; 
int arr[MAXN];

bool judge(int n, int m, int distance){
	int current = arr[0];//第一头牛放在第一个位置 
	int number = 1;//记录放的牛的数量
	for(int i = 1;i < n; ++i){
		if(arr[i] - current >= distance){
			number++;
			current = arr[i];
		}
		if(number >= m){
			return true;
		}
	} 
	return false;
}

int main()
{
	int n,m;
	while(scanf("%d%d",&n,&m) != EOF){
		for(int i = 0;i < n; ++i){
			scanf("%d",&arr[i]);
		}
		sort(arr,arr+n);
		int left = 1;
		int right = arr[n-1] - arr[0];
		while(left <= right){
			int middle = (left+right)/2;
			if(judge(n,m,middle)){
				left = middle + 1;
			}
			else{
				right = middle - 1;
			}
		}
		printf("%d",right);
		
	}
	
	return 0;
 } 

内容总结

以上是互联网集市为您收集整理的贪心算法——疯狂的牛牛全部内容，希望文章能够帮你解决贪心算法——疯狂的牛牛所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---