PAT乙級—1055. 集體照 (25)-native

拍集體照時隊形很重要，這裡對給定的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

思路：定義一個結構體數組，對結構體數組進行排序，然後依次從數組中取一排，對這一排進行符合題意的排序。注意：Amy與Tim身高相同，則Amy高。

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
struct Student{
    char name[];
    int height;
};
bool Cmp(Student s1,Student s2){
    if(s1.height!=s2.height){       //身高不相同，身高矮的在前
        return s1.height<s2.height;
    }
    else return strcmp(s1.name,s2.name)>;//身高相同，比較名字，字典序大的在前
}   
void output(Student s[],int begin,int end){//對每一排進行符合要求的排序并輸出
    Student temp[end-begin+];//注意此處數組的大小
    int m=(end-begin)/+;  
    int count_left=;       //左邊到了第幾個
    int count_right=;      //右邊到了第幾個
    bool should_right=false;//是否該右邊了
    for(int i=end;i>=begin;i--){
        if(i==end)  temp[m]=s[i];//先把最大值放在中間
        else{
            if(should_right){
                count_right++;
                temp[m+count_right]=s[i];
                should_right=false; 
            }
            else{
                count_left--;
                temp[m+count_left]=s[i];
                should_right=true;
            }       
        }   
    }
    for(int i=m+count_left;i<=m+count_right;i++){
        if(i!=(m+count_left))   cout<<" ";
        cout<<temp[i].name;
    }   
    cout<<endl;
}
int main(){
    int N,K;
    Student s[];
    cin>>N>>K;
    char name[];
    int height;
    for(int i=;i<=N;i++){  //為了每一排排序計算中間值的友善，從1開始
        cin>>s[i].name>>s[i].height;
    }
    sort(s+,s+N+,Cmp);
    int last=(K-)*(N/K)+;//計算出最後一排開始的元素
    output(s,last,N);   
     for(int i=last-N/K;i>=;i-=N/K)//輸出除了最後一排的元素
        output(s,i,i+N/K-);
    return ;
}
           

題目連結：

https://www.patest.cn/contests/pat-b-practise/1055