PAT Basic Level 1055 集体照解题思路及AC代码 v1.0

本文主要是介绍PAT Basic Level 1055 集体照解题思路及AC代码 v1.0，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

PAT 乙级 1055 集体照 v1.0

- 1. 题目简述及在线测试位置
- 2. 基本思路
- 3. AC代码

1. 题目简述及在线测试位置

1.1 给定人数N 和人员的姓名和身高信息，将这些人排成K行，每行人数为 N/K、最后一行人数为 N/K + N%K。排序规则是：A. 后排所有人的个子都不比前排任何人矮（非递增）B.每排中最高者站中间中间=排人数÷2 + 1 C.每排其他人以中间人为轴，按身高非增序，先左后右交替入队站在中间人的两侧（面对照相者视角）D.若身高相同，按名字的字典序升序排列
1.2 在线测试位置： 1055 集体照

2. 基本思路

2.1 使用结构体数组存储信息。对该结构体数组进行排序：首先按身高降序排列，其次按姓名升序排列(a->z) （排序规则 A D）
2.2 依次取出最后一排、次后一排 … 最前排的人员（面对照相者视角），对每排人员按规则 B C 进行排序并存储到 string类型数组中（存放人员姓名），信息存储完毕后，打印数组
2.3 注意：I. 结构体数组排序，需要严格按照 “首先按身高降序排列，其次按姓名升序排列” 完成排序 II. string类型数组的最大值应该设定≥10001，因为当有10000个人且仅一排时，最大编号是10000

3. AC代码

#include <algorithm>
#include <iostream>
using namespace std;#define MAX 10001 //当有10000个人 且仅一排时，从1到10000编号，数组范围a[10001]struct People
{string name;int height;
};bool compare(struct People a, struct People b)
{if (a.height != b.height)return a.height > b.height;elsereturn a.name < b.name; //首先按身高降序排列，然后按姓名升序排列(a->z)
}void Row_Sort(struct People human[], int Start, int End);int main()
{struct People human[MAX];int Number, Row, Row_People, LastRow_People;//总人数 排数 每排人数 最后排人数cin >> Number >> Row;Row_People = Number / Row;LastRow_People = Row_People + Number % Row;string Name;  int Height; //姓名 身高for(int i=0;i<Number;i++){cin >> Name >> Height;human[i].name = Name;human[i].height = Height;}sort(human, human + Number, compare);int Start = 0;Row_Sort(human, Start, Start + LastRow_People - 1);//最后一排Start = Start + LastRow_People;for (int i = 0; i < Row - 1; i++) // 次后一排 到 第一排{	Row_Sort(human, Start, Start + Row_People - 1);Start = Start + Row_People;}return 0;
}void Row_Sort(struct People human[], int Start, int End)
{int S = Start, E = End, Sum = End - Start + 1;string a[MAX]; //数组a存储排序后的人名int Middle = Sum / 2 + 1, Increase = 1; //数组a有效计数从1开始、以Sum结尾bool flag = true;//每排其他人以中间人为轴，按身高非增序，先 - 后 + 交替入队站在中间人的两侧a[Middle] = human[S].name;  //排中间的人for (int i = S+1; i <= E; i++){if (flag){a[Middle - Increase] = human[i].name;//先减flag = false;}else{a[Middle + Increase] = human[i].name;//后加flag = true;Increase++;}}cout << a[1];for (int i = 2; i <= Sum; i++)cout<<" " << a[i];cout << endl;return;
}