1109 Group Photo

题意：模拟队伍的排列。给出n个人，要求排成k排，每排人数必须为n/k，剩余的排在最后一排。第(i+1)排的人不得矮于第i排的人，每一排当中，最高的人排在center=m/2+1，第二高的排在最高者的左边，第三高的排在最高者的右边...以此类推。要求输出队伍排列。

思路：首先根据题目规则排序，然后确定每排的人数，前k-1排的人数为m=n/k，最后一排的人数为n-m*(k-1)。然后从最后一排开始排队伍（假设共有row排，记最后一排为row-1），在每一排当中，先确定中间位置，即center=m/2+1，然后分别令left=center-1，right=center+1，同时对两侧进行排序（这么处理是关键，相当于two pointers的思想！），最后记得判断一下左边是不是还剩一个没排好的，因为当一排的人数为偶数个时，最后一个是不成对的！

ps:纯粹的模拟，侧重考察代码功底，coding能力较弱的就比较耗时间，比如说我。。。要勤加练习。

代码：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N=10005;

struct Person{
    string name;
    int height;
}stu[N];

vector<int> format[N];//resulting formation

bool cmp(Person a,Person b){
    if(a.height!=b.height) return a.height>b.height;
    else return a.name<b.name;
}

int main()
{
    int n,k;
    cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>stu[i].name>>stu[i].height;
    }
    sort(stu,stu+n,cmp);

    //先确定每排的人数
    int cnt=n/k, row=0;
    while(row<k-1){//先排前k-1排
        format[row].resize(cnt+1);//每排的人数实则cnt，多申请一个空间是因为从下标1开始
        row++;
        n-=cnt;
    }
    format[row++].resize(n+1);//剩余的排在第k排

    int idx=0;
    for(int r=row-1;r>=0;r--){
        int m=format[r].size();
        m--;
        int center=(m/2)+1;//中间位置
        format[r][center]=idx++;
        int left=center-1,right=center+1;
        while(left>=1 && right<=m ){
            format[r][left]=idx++;
            left--;
            format[r][right]=idx++;
            right++;
        }
        if(left==1) format[r][left]=idx++;//当一排人数为偶数个时
    }

    //output
    for(int r=row-1;r>=0;r--){
        for(int c=1;c<format[r].size();c++){
            int i=format[r][c];
            cout<<stu[i].name;
            if(c<format[r].size()-1) cout<<' ';
            else cout<<'\n';
        }
    }
    return 0;
}