题目

拍集体照时队形很重要，这里对给定的 $N$ 个人 $K$ 排的队形设计排队规则如下：

  • 每排人数为 $N/K$ （向下取整），多出来的人全部站在最后一排；

  • 后排所有人的个子都不比前排任何人矮；

  • 每排中最高者站中间（中间位置为 $m/2+1$ ，其中 $m$ 为该排人数，除法向下取整）；

  • 每排其他人以中间人为轴，按身高非增序，先右后左交替入队站在中间人的两侧（例如5人身高为190、188、186、175、170，则队形为175、188、190、186、170。这里假设你面对拍照者，所以你的左边是中间人的右边）；

  • 若多人身高相同，则按名字的字典序升序排列。这里保证无重名。

现给定一组拍照人，请编写程序输出他们的队形。

输入格式：

每个输入包含 1 个测试用例。每个测试用例第 1 行给出两个正整数 $N$ （ $\le 10^4$ ，总人数）和 $K$ （ $\le 10$ ，总排数）。随后 $N$ 行，每行给出一个人的名字（不包含空格、长度不超过 8 个英文字母）和身高（[30, 300] 区间内的整数）。

输出格式：

输出拍照的队形。即K排人名，其间以空格分隔，行末不得有多余空格。注意：假设你面对拍照者，后排的人输出在上方，前排输出在下方。

输入样例：

1
2
3
4
5
6
7
8
9
10
11

10 3
Tom 188
Mike 170
Eva 168
Tim 160
Joe 190
Ann 168
Bob 175
Nick 186
Amy 160
John 159

输出样例：

1
2
3

Bob Tom Joe Nick
Ann Mike Eva
Tim Amy John

思路

  • 利用qsort排序，排序按照身高降序，身高相同按照名字字典序升序；
  • 第一行人数为 $N - N / K (K - 1)$ ，剩下每一行人数为 $N / K$ ；
  • 每一行从左开始先倒序输出奇数位的人名，再顺序输出偶数位的人名。这里按照已排好的顺序从0计数。e.g. 输出7个人名就是5 3 1 0 2 4 6，
  • 在处理空格的时候，奇数部分是不用担心的，只需在偶数部分判断最后一位；
  • 最大的奇数是（C语言除法） 一行总人数 / 2 * 2 - 1。

代码

Github最新代码，欢迎交流

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct student{
	char name[9];
	int height;
}student, *Student;

int cmp(const void *a, const void *b)
{
	Student s1 = *(Student*)a;
	Student s2 = *(Student*)b;
	if (s1->height != s2->height)
		return s2->height - s1->height;
	return strcmp(s1->name, s2->name);
}

/**
 * Print one row
 * Return the address of the beginning of next line
 **/
Student *printrow(Student *s, int num)
{
	for (int i = num / 2 * 2 - 1; i > 0; i -= 2)  /* the left half */
		printf("%s ", s[i]->name);
	for (int i = 0; i < num; i += 2)              /* the right half */
		printf("%s%c", s[i]->name, i + 2 < num ? ' ' : '\n');
	return s + num;
}

int main()
{
	/* read and sort data */
	int N, K;
	student students[10000] = {0};
	Student sp[10000] = {0}, *p = sp;

	scanf("%d %d", &N, &K);
	for (int i = 0; i < N; i++) {
		sp[i] = students + i;
		scanf("%s %d", sp[i]->name, &sp[i]->height);
	}

	qsort(sp, N, sizeof(Student), cmp);

	/* print */
	p = printrow(p, N - N / K * (K - 1));   /* the last row */
	while (p < sp + N)
		p = printrow(p, N / K);

	return 0;
}