PAT甲级1109.

目录

A1109

题目

样例

输入:

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

思路和坑点

　　思路：
　　显然这里需要对学生进行排序，根据排序结果进行位置的安排。第一步需要确定每一排的人数，因为剩余的直接都放在最后一排。假如我们以摄影师的角度看待学生位置，先放中间，然后再放摄影师角度的左边，再放摄影师角度的右边，直到这一排的学生放置满员。这里给出的思路是使用双指针，先放中间位置，然后依次放两次，判断边界就是左侧放置完毕，因为按照题目给出的条件，摄影师角度的左侧人数一定小于大于等于右侧，所以只需要判断左侧即可。

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef struct student{                     //学生信息结构体，名字和身高
    string name;
    int high;
}STU;
bool cmp(STU &a,STU &b){                    //对学生的排序函数，先根据身高从高到低排序，再根据名字字典序排序
    if(a.high!=b.high) return a.high>b.high;
    else return a.name<b.name;
}
int main(){
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt", "r", stdin);
#endif 
    int N,K;
    scanf("%d %d",&N,&K);
    STU DATA[N];
    for(int i=0;i<N;i++)                    //读入数据
        cin>>DATA[i].name>>DATA[i].high;
    sort(DATA,DATA+N,cmp);                  //按照身高从高到低排序，同身高按照名字字典序排列
    vector< vector<string> > out(K);        //输出的二维数组
    int num=N/K;                            //计算每一排人数
    for(int i=0;i<K;i++){                   //初始化每一排数组大小
        if(i==0) out[i].resize(N-(K-1)*num);//如果有剩余放在最后一排
        else out[i].resize(num);
    }
    num=0;                                  //遍历学生数组的指针
    for(int i=0;i<K;i++){                   
        int cnt=out[i].size();              //获取每一排人数
        int mid=cnt/2;                      //计算中间位置，题目中从1开始，如果这里用下标表示，则恰好不用+1
        out[i][mid]=DATA[num++].name;       //放置中间位置
        int l=mid,r=mid;                    //左右两侧的位置指针，初始化为中间位置
        while(1){
            l--,r++;                        
            if(l>=0) out[i][l]=DATA[num++].name;    //在合法范围内放置，先放置摄影师视角的左侧
            if(r<cnt)out[i][r]=DATA[num++].name;    //再放置摄影师视角的右侧
            if(l<0) break;                  //显然左侧的人数大于等于右侧（以摄影师视角的左右侧），所以只判定左侧到达边界说明这一排站位结束
        }
    }
    for(int i=0;i<K;i++){                   //输出结果并控制格式
        for(int j=0;j<out[i].size();j++){
            if(j) putchar(' ');
            cout<<out[i][j];
        }
        putchar('\n');
    }
    return 0;
}