个人练习-PAT甲级-1109 Group Photo_综合

题目链接https://pintia.cn/problem-sets/994805342720868352/problems/994805360043343872

题目大意：一群人拍照，排序是从高到矮，字母顺序。给出人数和行数，输出每行拍照的人。除不尽人的放第一行。要求最高的在中间，然后放左边、放右边…

思路：容易得出每行的人数sz，只有第一行可能多一点，其他的每行人数都一样，所以从高到低排序后分割成一行一行来看。

给排序后的人标号从0到N-1。假设本行的人序号从start到end，那么先算出C位的序号center，根据人数sz奇偶分情况来。

        int sz, end, center;if (i != 0) sz = p_num;else sz = p1;end = start + sz - 1;if (sz % 2 == 0) center = (start + end) / 2 + 1;else center = (start + end) / 2;

之后换算本行的人拍照的顺序。不妨先看start=0的情况，给出奇、偶两种例子

0 1 2 3 43 1 0 2 4

0 1 2 33 1 0 2

可见在碰到center之前，结果的顺序号都为奇数，在center处为0，在center后都为偶数。那么找找规律一算就行了。

然后考虑偏移，所有结果加上一个start。循环末尾记得给更新start

        int pos;for (pos = start; pos < center; pos++)trans[pos] = 2 * (center - pos) - 1 + start;for (; pos <= end; pos++)trans[pos] = 2 * (pos - center) + start;for (pos = start; pos <= end; pos++) {
    if (pos != start)cout << " " << stu[trans[pos]].name;elsecout << stu[trans[pos]].name;}cout << endl;start += sz;

完整代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <set>using namespace std;class Ppl{
    
public:string name;int height;
};vector<Ppl> stu;
vector<int> trans;bool cmp(Ppl x, Ppl y) {
    if (x.height != y.height)return x.height > y.height;elsereturn x.name < y.name;
}int main() {
    int N, K;scanf("%d %d", &N, &K);stu.resize(N);trans.resize(N);for (int i = 0; i < N; i++)cin>>stu[i].name>>stu[i].height;sort(stu.begin(), stu.end(), cmp);int p_num = N / K;int p1 = p_num + N % K;int start = 0;for (int i = 0; i < K; i++) {
    int sz, end, center;if (i != 0) sz = p_num;else sz = p1;end = start + sz - 1;if (sz % 2 == 0) center = (start + end) / 2 + 1;else center = (start + end) / 2;int pos;for (pos = start; pos < center; pos++)trans[pos] = 2 * (center - pos) - 1 + start;for (; pos <= end; pos++)trans[pos] = 2 * (pos - center) + start;for (pos = start; pos <= end; pos++) {
    if (pos != start)cout << " " << stu[trans[pos]].name;elsecout << stu[trans[pos]].name;}cout << endl;start += sz;}return 0;
}