1055. 集体照 (25)

待我称王封你为后i 2022-05-26 08:36 185阅读 0赞

拍集体照时队形很重要，这里对给定的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

**输出样例：**

Bob Tom Joe Nick
    Ann Mike Eva
    Tim Amy John

--------------------

代码：

#include<stdio.h>
    #include<vector>
    #include<algorithm>
    #include<string.h>
    #include<string>
    using namespace std;
    vector<struct node> v;
    struct node
    {
        char name[10];
        int heigh;
    };
    bool cmp(struct node a,struct node b)
    {
        if(a.heigh!=b.heigh)
            return a.heigh>b.heigh;
        else
            return strcmp(a.name,b.name)<0;
    }
    int main()
    {
        int i,j,n,m,k,t,l=0,c;
        scanf("%d %d",&n,&m);
        for(i=0;i<n;i++)
        {
            struct node tmp;
            scanf("%s %d",tmp.name,&tmp.heigh);
            v.push_back(tmp);
        }
        sort(v.begin(),v.end(),cmp);
        if(n/m==0)
        {
            for(i=0;i<n;i++)
            {
                printf("%s\n",v[i].name);
            }
            return 0;
        }
        for(i=0;i<m;i++)
        {
            vector<struct node> ansv(n+1);
            if(i==0)
            {
                k=n/m+n%m;
                t=k/2+1;
                for(j=0;;j++)
                {
                    if(j==0)
                    {
                       ansv[t]=v[l++];
                    }
                    else
                    {
                        if(t-j>=1)
                    {
                        ansv[t-j]=v[l++];
                    }
                    else
                    {
                        break;
                    }
                    if(t+j<=k)
                    {
                        ansv[t+j]=v[l++];
                    }
                    else
                    {
                        break;
                    }
                    }
                }
                for(j=1;j<=k;j++)
                {
                    if(j==1)
                    {
                        printf("%s",ansv[j].name);
                    }
                    else
                    {
                        printf(" %s",ansv[j].name);
                    }
                }
                printf("\n");
            }
            else
            {
                k=n/m;
                t=k/2+1;
                for(j=0;;j++)
                {
                    if(j==0)
                    {
                       ansv[t]=v[l++];
                    }
                    else
                    {
                        if(t-j>=1)
                    {
                        ansv[t-j]=v[l++];
                    }
                    else
                    {
                        break;
                    }
                    if(t+j<=k)
                    {
                       ansv[t+j]=v[l++];
                    }
                    else
                    {
                        break;
                    }
                    }
                }
                for(j=1;j<=k;j++)
                {
                    if(j==1)
                    {
                        printf("%s",ansv[j].name);
                    }
                    else
                    {
                       printf(" %s",ansv[j].name);
                    }
                }
                printf("\n");
            }
        }
        return 0;
    }