数据结构与算法

题目描述

农夫约翰搭了一间有N(2 <= N <= 100,000)间牛社的小屋。牛舍排在一条直线上，第i号牛舍在xi(0 <= xi <= 1,000,000,000)的位置，但是他的M(2 <= M <= N)头小牛对小屋很不满意，因此经常互相攻击。约翰为了防止牛之间互相伤害，因此决定把每头牛都放在离其他牛尽可能远的牛舍。也就是最大化最近的两头牛之间的距离。

样例输入 N=5, M=3, x={1,2,8,4,9} 样例输出 3(在位置1,4,9放3头牛)

如果采用回溯法，n个里生成m个直接上代码

#include <bits/stdc++.h>
using namespace std;

int a[100],pos[100],n,m,ans = 0;
int array_ans[100];
bool use[100] = {false};

int MIN(int pos[])
{
	int min = 0x3fffffff;
	for(int i = 1; i<=m-1; i++)
	{
		if(a[pos[i+1]]-a[pos[i]] < min) 
		min = a[pos[i+1]]-a[pos[i]];
	}
	return min;
}

void niupeng(int k,int p)
{
	if(k>m) 
	{
		if (MIN(pos)>ans) 
		{
			ans = MIN(pos);
			for(int i = 1;i<=m; i++)
			{
				array_ans[i] = a[pos[i]];
			}	
		}
		return;
	}
	for(int i = p; i<=n; i++)
	if(use[i]==false)
	{
		use[i] = true;
		pos[k] = i;
		niupeng(k+1,i);
		use[i] = false;
	}
}

int main()
{
	cin >> n >> m;
	for (int i = 1; i<=n; i++)
	{
		cin >> a[i];
	}
	sort(a,a+n);
	niupeng(1,1);
	
	for(int i = 1; i<=m; i++)
	{
		cout << array_ans[i] <<" ";
	}
	
}