PAT A1109 Group Photo(C++)

PAT甲级目录 | PAT乙级目录

题目描述

原题地址:A1109 Group Photo
中文版:B1055 集体照

解题思路

对所有人逆序排序,先从最后一排开始排,每排完一排就输出。对于每一排,计算该排人数,并设置对应的左右指针,一边排一边移动指针,当指针达到边界,则该排完成,按指定格式输出结果。

易错点

  • if(i == 0) m = n - (n / k) * (k - 1);
    • 最后一排人数
  • 对于拍照的人(输出格式)来说,从中间开始,先排右边的人,再排左边的人。
  • r = m / 2; l = r - 1;
    • 设置好左右指针位置,免去考虑第一个人是否重复赋值
  • 一共 k 排,因此遍历范围正好为 [0, k)

也许陌生的知识点

  • sort(S, S + n, cmp);
    • 排序函数,实现 [first, last) 范围内的排序,可以自定义排序策略 cmp 函数
    • 不带 cmp 参数的 sort 函数实现从小到大排序
    • 所需头文件: algorithm

代码示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct Stu{
char name[20];
int h;
}S[10010];
bool cmp(Stu a, Stu b){
if(a.h != b.h) return a.h > b.h;
else return strcmp(a.name, b.name) < 0;
}
int main(){
int n, k, cnt = 0;
scanf("%d %d", &n, &k);
for(int i = 0; i < n; i++) scanf("%s %d", &S[i].name, &S[i].h);
sort(S, S + n, cmp);
for(int i = 0, m, l, r; i < k; i++){// 总共 k 排
int ans[10010] = {0};
if(i == 0) m = n - (n / k) * (k - 1); //计算本排人数
else m = n / k;
r = m / 2; // 设置左右指针
l = r - 1;
while(r < m || l >= 0){ // 一边移动指针一边记录编号
if(r < m) ans[r++] = cnt++;
if(l >= 0) ans[l--] = cnt++;
}
for(int j = 0; j < m; j++){
if(j != 0) printf(" ");
printf("%s", S[ans[j]].name);
if(j == m - 1) printf("\n");
}
}
return 0;
}