1055. 集体照

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

• 每排人数为N/K（向下取整），多出来的人全部站在最后一排；
• 后排所有人的个子都不比前排任何人矮；
• 每排中最高者站中间（中间位置为m/2+1，其中m为该排人数，除法向下取整）；
• 每排其他人以中间人为轴，按身高非增序，先右后左交替入队站在中间人的两侧（例如5人身高为190、188、186、175、170，则队形为175、188、190、186、170。这里假设你面对拍照者，所以你的左边是中间人的右边）；
• 若多人身高相同，则按名字的字典序升序排列。这里保证无重名。

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

输入格式：

每个输入包含1个测试用例。每个测试用例第1行给出两个正整数N（<=10000，总人数）和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

---

解题思路：
先对录入的数据进行排序，按身高非增序，身高相同的按字典顺序排序。排序的条件利用 qsort 的比较函数来控制。

观察知对每排的输出除了最后一排外基本相同，因此可将输出写成函数，方便调用。

假设一排有 row 个元素，则新建一个 row 个大小的字符数组 a，存放当前排的姓名。然后将排序好的数组依次复制进来，首先将最大值复制到 a[mid] 中，再按照题目规则即先左后右地依次放入到数组 a 中，函数传入了起始复制范围和终止复制范围，意在将此作为循环出口的判断条件。最后输出即可。

图示：

解题代码：

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

struct info {
    char name[9];
    int height;
};

int compare(const void *p, const void *q);
int arrange (struct info stu[], int row, int start, int end);

int main() 
{    
    int N, K;
    scanf("%d %d\n", &N, &K);
    int row = N / K; // 每排人数 
    int last_row =  row + (N - row * K); // 最后排的人数 
    struct info stu[N];
    for (int i=0; i<N; i++) {
        scanf("%s %d", &stu[i].name, &stu[i].height);
    }
    qsort(stu, N, sizeof(struct info), compare);
    
    int end = arrange(stu, last_row, 0, last_row); // 单独处理最后排的人 
    for (int i=1; i<K; i++) {
        end = arrange(stu, row, end, end+row);
    } // 处理其他排 
    
    return 0;
} 

int compare(const void *p, const void *q) {
    int x = (*(struct info *)p).height;
    int y = (*(struct info *)q).height;
    if (x > y) {
        return -1;
    } else if (x < y){
        return 1;
    } // 按身高排序 
    char *s = (*(struct info *)p).name;
    char *t = (*(struct info *)q).name;
    if (strcmp(s, t) > 0) {
        return 1;
    } else if (strcmp(s, t) < 0){
        return -1;
    } // 身高相同，按姓名排序 
    return 0;
}

int arrange (struct info stu[], int row, int start, int end) {
    char a[row][9];
    int mid = row / 2;
    int left = mid-1, right = mid+1;
    strcpy(a[mid], stu[start++].name);
    while (start < end) {
        if (left >= 0) {
            strcpy(a[left--], stu[start++].name);
        }
        if (right < row) {
            strcpy(a[right++], stu[start++].name);
        }
    }
    for (int i=0; i<row-1; i++) {
        printf("%s ", a[i]);
    }   
    printf("%s\n", a[row-1]);
    return end; // 返回本次的终点作为下次的起点 
}