PAT甲题题解-1109. Group Photo (25)-（模拟拍照排队）

题意：n个人，要拍成k行排队，每行 n/k人，多余的都在最后一排。

从第一排到最后一排个子是逐渐增高的，即后一排最低的个子要>=前一排的所有人

每排排列规则如下：

1.中间m/2+1为该排最高；

2.其他人按各自降序顺序，轮流排到中间最高的左边和右边；

举个例子 190 188 186 175 170

— — 190 — —

— 188 190 — —

— 188 190 186 —

175 188 190 186 —

175 188 190 186 170

3.当个子一样高时，名字按字典序顺序，靠前的先排入队伍。

纯粹模拟，没啥好说的。

#include <iostream>
#include <cstdio>
#include <string.h>
#include <algorithm>
using namespace std;
const int maxn=10000+5;


struct People{
    char str[20];
    int height;
    bool operator<(const People tmp)const{
        if(height==tmp.height){
            if(strcmp(str,tmp.str)<0)
                return false;
            else
                return true;
        }
        else{
            return height<tmp.height;
        }
    }
}people[maxn];
int main()
{
    int k,n;
    scanf("%d %d",&n,&k);
    int ans[k+1][maxn];
    int cols[k+1];
    for(int i=0;i<n;i++){
        scanf("%s %d",people[i].str,&people[i].height);
    }
    sort(people,people+n);

    int m=n/k;
    int left,right;
    for(int i=1;i<=k;i++){
        left=(i-1)*m;
        right=i*m-1;
        if(i==k){
            m=n-(k-1)*m;
            right=n-1;
        }
        cols[i]=m;
        int center=m/2+1;
        int idx=right;
        ans[i][center]=idx;
        idx--;
        int l=center-1,r=center+1;
        while(r<=m){
            ans[i][l]=idx;
            idx--;
            ans[i][r]=idx;
            idx--;
            l--;r++;
        }
        if(l==1)
            ans[i][1]=idx;
    }
    for(int i=k;i>=1;i--){
        for(int j=1;j<=cols[i];j++){
            if(j==01){
                printf("%s",people[ans[i][j]].str);
            }
            else{
                printf(" %s",people[ans[i][j]].str);
            }
        }
        printf("
");
    }
    return 0;
}