1055 集体照（JAVA）

ゝ一世哀愁。 2023-09-28 18:55 28阅读 0赞

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

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

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

#### 输入格式： ####

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

#### 代码实现： ####

import java.io.*;
    import java.util.Arrays;
    //非常巧妙的方法：
    //https://blog.csdn.net/A1sakaTaiga/article/details/122044190
    /**
     * @author yx
     * @date 2022-07-22 13:45
     */
    public class Main {
        static PrintWriter out=new PrintWriter(System.out);
        static BufferedReader ins=new BufferedReader(new InputStreamReader(System.in));
        static StreamTokenizer in=new StreamTokenizer(ins);
    
        static class Node implements Comparable<Node>{
            String name;
            int tall;
            Node(String name,int tall){
                this.name=name;
                this.tall=tall;
            }
    
            @Override
            public int compareTo(Node o) {
                //采用自定义身高的降序排序
                if(this.tall>o.tall){
                    return -1;
                }else if(this.tall<o.tall){
                    return 1;
                }else {//当身高相同的情况下，采用名字的升序排序
                    return this.name.compareTo(o.name);
                }
            }
        }
        public static void main(String[] args) throws IOException {
            in.nextToken();
            int n=(int) in.nval;//人数
            in.nextToken();
            int m=(int) in.nval;//排数
            int k=n/m;//除最后一排，每一排的人数
            Node[] nodes=new Node[n];
            for (int i = 0; i < n; i++) {
    //            String[] split=ins.readLine().split(" ");
                in.nextToken();
                String name=in.sval;
                in.nextToken();
                int tall=(int) in.nval;
                nodes[i]=new Node(name,tall);
            }
            Arrays.sort(nodes);
            int m_start=0;//每一排结尾的指针
            int m_end=0;//每一排的开头的指针
            while (m_end < n){
                m_start=m_end;//
                if(m_end==0){//最后一排开始
                    m_end=k+(n-k*m);
                }else {
                    m_end+=k;
                }
                int length=m_end-m_start;
                String[] s=new String[length];//定义大小为每一排人数的数组
                int mid=length/2;//数组中间位置（下标从0开始算）
                for (int i = m_start; i <m_end ; i++) {
                    //先左后右交替排序
                    // mid  然后 mid-1 然后 mid -1 +2 然后 mid -1 +2 -3....先左再右
                    mid+=(int) Math.pow(-1,i-m_start)*(i-m_start);
                    s[mid]=nodes[i].name;
                }
                 for (int i = 0; i <length-1 ; i++) {
                    out.print(s[i]+" ");
                }
                out.println(s[length-1]);
            }
            out.flush();
        }
    }