PAT A1109 Group Photo(C++)

发表于 | 分类于 | |
字数统计: 478 字 | 阅读时长 ≈ 2 分钟
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;
}