士兵站队问题代码,C代码库,德仔网

代码语言

代码分类

【C】士兵站队问题

作者:陨落人间 / 发布于2015/8/3/ 735

在一个划分成网格的操场上，n个士兵散乱地站在网格点上，网格点由整数坐标（x,y）表示。士兵们可以沿网格边上下左右移动一步，但在同一时刻任一网格点上只能有一名士兵。按照军官的命令，士兵们要整齐的列成一个水平队列，即排列成（x,y），（x+1,y），。。。，（x+n-1,y）。如何选择x,y的值才能使得士兵们以最少的总移动步数排成一列？计算使所有士兵排成一列所需要的最少移动步数。 VC++6.0


	#include<math.h>
	#include<iostream.h>
	#include<cstdio>
	#include<algorithm>
	#include<time.h>
	using namespace std;
	void main()
	{
	 clock_t start,finish;
	 start=clock();
	 freopen("in.txt","r",stdin);
	 freopen("out.txt","w",stdout);
	 short x[10000],y[10000];
	 short n,a,i,j,miny(0),minx(0);
	 cin>>n;
	 for(i=1;i<=n;i++)
	 cin>>x[i]>>y[i];
	 sort(x+1,x+n+1);
	 sort(y+1,y+n+1);
	 for(i=2;i<=n;i++)
	 miny+=(y[i]-y[1]);
	 if(x[1]==x[2])
	 {
	 i=3;
	 j=1;
	 while(x[i]==x[1])
	 {
	 i++;
	 j++;
	 }
	 x[0]=j;
	 }
	 for(i=1;i<=n;i++)
	 minx+=abs(x[i]-(x[1]-x[0]+i-1));
	 for(i=2;i<=n;i++)
	 {
	 short k(0);
	 for(j=1;j<=n;j++)
	 k+=abs(y[j]-y[i]);
	 if(miny>k)
	 miny=k;
	 }
	 for(i=x[1]-x[0]+1;i<=x[n/2];i++)
	 {
	 short k(0);
	 for(j=1;j<=n;j++)
	 k+=abs(x[j]-(i+j-1));
	 if(minx>k)
	 minx=k;
	 }
	 miny+=minx;
	 cout<<miny<<endl;
	 finish=clock();
	 double during=(double)(finish - start)/CLOCKS_PER_SEC;
	 cout<<during<<endl;
	 fclose(stdin);
	 fclose(stdout);
	}

评论列表

本站所提供的代码，版权归原作者所有，若有侵犯作者版权，请与我们联系，我们将立即删除或修改。谢谢!
本站所有代码发布及提供者。

试试其它关键字

　士兵站队　

同语言下

可能有用的

陨落人间贡献的其它代码(4)