PAT-BASIC1055——集体照PAT-ADVANCED1109——Group Photo

我的PAT-BASIC代码仓

https://github.com/617076674/PAT-BASIC

我的PAT-ADVANCED代码仓

https://github.com/617076674/PAT-ADVANCED

原题链接

PAT-BASIC1055

https://pintia.cn/problem-sets/994805260223102976/problems/994805272021680128

PAT-ADVANCED1109

https://pintia.cn/problem-sets/994805342720868352/problems/994805360043343872

题目描述

PAT-BASIC1055

PAT-ADVANCED1109

知识点

排序

思路

（1）定义一个学生结构体，存放名字和身高。

（2）计算每行的学生人数，最后一行需要特殊处理。

（3）自定义学生结构体的比较函数，按题目给的排序规则对学生进行排序处理。

（4）按照行数，对学生进行分组，按题目规则打印每一行的学生名字，需要注意的是，最后一行反而是最先输出的。

（5）定义一个显示单行学生的函数。按题目所述，该函数先把最高的学生放在一行的中间位置，再用两个指针left和right标记将要放置的左边和右边的位置，按身高降序依次排列学生即可。

注意点

左右相反，题目说了一排中确定最高者位置后先右后左站在中间人的两侧，由于我们面对着拍照者，在代码实现中应该是先左后右站在中间人的两侧。

复杂度分析

时间复杂度是O(NlogN)。空间复杂度是O(N)。

C++代码

#include<iostream> #include<algorithm> #include<cstring> #include<vector> using namespace std; struct person{ //存储人名和身高 char name[9]; int height; }; bool cmp(person p1, person p2); //按升高降序排序，若身高相同，则按人名升序排序 void showPeople(vector<person> row); //显示每一行的人名 int main(){ int N, K; scanf("%d %d", &N, &K); //读取总人数和总行数 person people[N]; for(int i = 0; i < N; i++){ scanf("%s %d", people[i].name, &people[i].height); //读入每个人的人名和身高 } sort(people, people + N, cmp); //按身高从高到低排序 int otherRow = N / K; //除最后一行的每行人数 int lastRow = N - otherRow * (K - 1); //最后一行的人数 vector<person> row; //存储每行的人 for(int i = N - 1; i >= N - lastRow; i--){ row.push_back(people[i]); //最后一行 } showPeople(row); //先输出最后一行的人名 for(int i = 0; i < K - 1; i++){ row.clear(); //开始新的一行前先清空row for(int j = N - lastRow - 1 - otherRow * i; j >= N - lastRow - otherRow * (i + 1); j--){ //按每行otherRow个人对people数组中的数据进行分行 row.push_back(people[j]); //其他行 } showPeople(row); //输出其他行的人名 } return 0; } bool cmp(person p1, person p2){ if(p1.height == p2.height){ return strcmp(p1.name, p2.name) > 0; }else{ return p1.height < p2.height; } } void showPeople(vector<person> row){ int size = row.size(); person people[size]; int mid = size / 2; //确定最高者的位置，索引从0开始 people[mid] = row[0]; int left = mid - 1; //确定最高者左边的下一个位置 int right = mid + 1; //确定最高者右边的下一个位置 for(int i = 1; i < size; i++){ if(i % 2 == 1){ //先放左边 people[left--] = row[i]; }else{ //再放右边 people[right++] = row[i]; } } for(int i = 0; i < size; i++){ //输出每行人名 printf("%s", people[i].name); if(i != size - 1){ printf(" "); }else{ printf("\n"); } } }

C++解题报告