一、题目
拍集体照时队形很重要,这里对给定的 N 个人 K 排的队形设计排队规则如下:
每排人数为 N/K(向下取整),多出来的人全部站在最后一排;
后排所有人的个子都不比前排任何人矮;
每排中最高者站中间(中间位置为 m/2+1,其中 m 为该排人数,除法向下取整);
每排其他人以中间人为轴,按身高非增序,先右后左交替入队站在中间人的两侧(例如5人身高为190、188、186、175、170,则队形为175、188、190、186、170。这里假设你面对拍照者,所以你的左边是中间人的右边);
若多人身高相同,则按名字的字典序升序排列。这里保证无重名。
现给定一组拍照人,请编写程序输出他们的队形。
输入格式:
每个输入包含 1 个测试用例。每个测试用例第 1 行给出两个正整数 N(≤10^4 ,总人数)和 K(≤10,总排数)。随后 N 行,每行给出一个人的名字(不包含空格、长度不超过 8 个英文字母)和身高([30, 300] 区间内的整数)。
输出格式:
输出拍照的队形。即K排人名,其间以空格分隔,行末不得有多余空格。注意:假设你面对拍照者,后排的人输出在上方,前排输出在下方。
输入样例:
10 3
Tom 188
Mike 170
Eva 168
Tim 160
Joe 190
Ann 168
Bob 175
Nick 186
Amy 160
John 159
输出样例:
Bob Tom Joe Nick
Ann Mike Eva
Tim Amy John
作者: CHEN, Yue
单位: 浙江大学
时间限制: 400 ms
内存限制: 64 MB
代码长度限制: 16 KB
二、思路
1、求每行人数:
mA=N/K;//每行人数
mB=N/K+N%K;//最后一行人数
2、分组排队
建立一个整形数组B[ K ][ mB ],按照队形,保存拍照人信息数组A[]中的坐标;
for(int i=0,n=0 ; i<K ; i++)
//K趟外循环,对应K排
for(int m= !i ? mB:mA,j=0,pos=m/2,flag=1 ; j<m ; j++,flag*=-1 )
//pos初始为m/2,是最高的那个人站的位置;
//m为每排人数;
//设五个人的身高按降序排序:A[5]={5,4,3,2,1}, m/2=2,最高的人放在B[i][m/2]=A[0]=5;
//j++并且乘-1,j=-1;第二高的人排在最高的人左边B[i][m/2+j]=A[1]=4;
//j++并且乘-1,j=2; 第三高的人排在最高的人右边B[i][m/2+j]=A[2]=3;
//...
//得到 B[i][]={2,4,5,3,1};
B[i][ pos+=j*flag ]=n++;//以上是方便理解,B中仅保存A中元素的下标;
根据B中的下标输出:
for(int i=0 ; i<K ; i++)
for(int j=0,m= !i ? mB:mA ; j<m ; j++ )
printf("%s%s",A[ B[i][j] ].Name , j<m-1 ? " " : "\n" );
三、代码实现
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
typedef struct
{
char Name[9];
int H;
}Data;
int cmp(const void * a,const void * b)
{
if( (*(Data *)a).H != (*(Data *)b).H )
return (*(Data *)b).H - (*(Data *)a).H;
else
return strcmp( (*(Data *)a).Name , (*(Data *)b).Name );
}
int main()
{
int N,K,mA,mB;
scanf("%d %d",&N,&K);
mA=N/K,mB=N/K+N%K;
Data A[N];
int B[K][mB];
for(int i=0 ; i<N ; i++)
scanf("%s %d",A[i].Name,&A[i].H);
qsort(A,N,sizeof(Data),cmp);
for(int i=0,n=0 ; i<K ; i++)
for(int m= !i ? mB:mA,j=0,pos=m/2,flag=1 ; j<m ; j++,flag*=-1 )
B[i][ pos+=j*flag ]=n++;
for(int i=0 ; i<K ; i++)
for(int j=0,m= !i ? mB:mA ; j<m ; j++ )
printf("%s%s",A[ B[i][j] ].Name , j<m-1 ? " " : "\n" );
}