youju.cpp

程序员2007年8月的解答。采用搜索算法排序和二次搜索算法验证。

// youju.cpp : Defines the entry point for the console application.
// <程序员>2007 年 8 月刊

#include "stdafx.h"
#define MAX 1024
struct struct_v
{
	int aixs;   //村子坐标
	int length; //最近邮局距离
}v[MAX];    
int p[MAX];      
int tmp_v[MAX];
int output_p[MAX];//用于最终输出
char used[MAX];   
int v0;
int p0;

int min(int a,int b)
{
	int z;
	z=a<b?a:b;
	return z;
}

void theminlength()//计算在某种邮局选择方法下,邮寄的最短距离
{	
int i=1;
int j=1;
int k=1;
int tmp_v0_length;
tmp_v0_length=0;
for(i=1;i<=v0;i++)  
{
v[i].length  =MAX;
}
for(i=1;i<=p0;i++)
{
	v[p[i]].length  =0;
}

while(j<=v0)         //正向一次搜索
{   
	if (j==p[k])
	{
		j++;
		k++;
		if (k>p0)
		break;
	}
	else
	{
	v[j].length =min((v[p[k]].aixs -v[j].aixs),v[j].length ) ;
	j++;
	}
}

j=v0;
k=p0;
while(j>=1)          //逆向一次搜索
{
	if(j==p[k])
	{
		j--;
		k--;
		if(k<1)
		break;
	}
	else
	{
		v[j].length =min((v[j].aixs -v[p[k]].aixs ),v[j].length );
		j--;
	}
}


for(i=1;i<=v0;i++)
{tmp_v0_length+=v[i].length ;
}
if (v[0].length >0)
{
if (tmp_v0_length<v[0].length )
{
	v[0].length =tmp_v0_length;
	for(int r=1;r<=p0;r++)
	{
		output_p[r]=p[r];
	}
}	
}
else
{ v[0].length =tmp_v0_length;
	for(int r=1;r<=p0;r++)
	{
		output_p[r]=p[r];
	}
}

return;
}

void combine(int pos)
{   int i;
	if(pos>p0)
	{
		theminlength();
		return;
	}
	for(i=(pos>1?(p[pos-1]+1):pos);i<=pos+v0-p0;i++)//组合每个数后面V0-p0个数
	{
    if(!used[i])
	{
		p[pos]=i;
		used[i]++;
		combine(pos+1);
		used[i]--;
	}
	}
}


int main(int argc, char* argv[])
{
	int tmp;
	int i=1;
    printf("输入 v 和 p\n");
	scanf("%d %d",&v0,&p0);
	tmp=v0;
	while(tmp-->0)
	{
		printf("输入 村子坐标:");
		scanf("%d",&v[i++].aixs); 
		printf("\n");
	}

	for (int j=1;j<=v0;j++)
	{
		tmp_v[j]=j;//排列初始值
	}
    combine(1);
	printf("%d:",v[0].length );
	for(int r=1;r<=p0;r++)
	{
		printf("%d ",v[output_p[r]]);
	}
	return 0;
}