完美旗手队列

完美旗手队列

时间: 1ms        内存:64M

描述:

YT大学定于5月16日举行校运动会。学校有 n 个系。组委会要求每个系有 m 个运动员参加开幕式,并且每个系的 m 个运动员站成一队。我们假设 n*m 名运动员站成一个nm列的队列,表示为Anm下图中的每一行代表一个系。

 

a11 a12 a13 a1m

a21 a22 a23 a2m

     

an1 an2 an3 anm

 

现组委会要求每系在 m 个运动员中选出一名旗手站在本系的前面,为了视觉上的美观要求相邻的旗手身高差距尽可能的小,形成一个完美旗手队列。比如我们从上述队列中选择出{a12, a24, a33, , ank}作为旗手队列。则这n个人的身高差最小的队列是完美旗手队列。比如有4个系,各系选择的旗手分别为a,b, c, d, val=|a-b|+|b-c|+|c-d| 最小的选择为完美旗手队列。你能帮YT大学选择完美旗手队列吗?

输入:

多个测试样例,每个测试样例第一行为两个整数n, m (1 <= n, m <= 1000) ,接着是n行整数数列,表示原始的队列,整数值表示运动员的身高(<=10000)。

输出:

对于每一个测试样例,输出最小的val值。

示例输入:

3 3
2 3 1
4 7 6
7 9 2

示例输出:

3

提示:

参考答案(内存最优[8772]):

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<algorithm>
using namespace std;
#define MIN(aa,bb) aa<bb?aa:bb
#define inf 1<<30
int n,m,cap[1010][1010];
int Min[1010][1010];
int main(){
	//freopen("1.in","r",stdin);
	//freopen("1.out","w",stdout);
	int i,j;
    while(scanf("%d%d",&n,&m)!=EOF){
    	  for(i=0;i<n;i++){
		      for(j=0;j<m;j++) scanf("%d",&cap[i][j]);
    	      sort(cap[i],cap[i]+m);
		  }
		  memset(Min,0,sizeof(Min));
		  for(i=1;i<n;i++){
  			  for(j=0;j<m;j++){
  			  	  Min[i][j]=inf;
		          int temp=lower_bound(cap[i-1],cap[i-1]+m,cap[i][j])-cap[i-1];
				  if(temp<m)
				     Min[i][j]=MIN(Min[i][j],Min[i-1][temp]+abs(cap[i-1][temp]-cap[i][j]));
  			      if(temp>0)
					 Min[i][j]=MIN(Min[i][j],Min[i-1][temp-1]+abs(cap[i-1][temp-1]-cap[i][j]));
              }
  		  }
  		  int ans=inf;
  		  for(i=0;i<m;i++) ans=MIN(ans,Min[n-1][i]);
  		  printf("%d\n",ans);
    }
	return 0;
}

参考答案(时间最优[433]):

#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int a[1003][1003];
int temp[1003]; 
int dp[1003][1003];
int m,n;
int min(int x,int y)
{
	return x<y?x:y;
}
int main()
{
	while(scanf("%d %d",&m,&n)!=EOF)
	{
		for(int i=0;i<m;i++)
	{
		for(int j=0;j<n;j++)
		{
			scanf("%d",&temp[j]);
		}
		sort(temp,temp+n);
		for(int j=0;j<n;j++)
		a[i][j]=temp[j];
	}
	for(int i=1;i<m;i++)
	{
		int k=0;
		for(int j=0;j<n;j++)
		{
			for(;k<n&&a[i-1][k]<a[i][j];k++)//
			{
				
			}
			if(k==0)
			{
				dp[i][j]=dp[i-1][k]+abs(a[i][j]-a[i-1][k]);
			}
			else if(k==n)
			{
				dp[i][j]=dp[i-1][k-1]+abs(a[i][j]-a[i-1][k-1]);
			}
			else
			{
				dp[i][j]=min(dp[i-1][k-1]+abs(a[i][j]-a[i-1][k-1]),dp[i-1][k]+abs(a[i][j]-a[i-1][k]));
			}
		}
	}
	int mini=9999999;
	for(int i=0;i<n;i++)
	{
		mini=min(mini,dp[m-1][i]);
	}
	printf("%d\n",mini);
	}
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注