关于c++:PAT甲级1109-Group-Photo

题目粗心

有 N 集体照相，现将 N 集体排成 K 行，每一行都有 N / K 集体，并依照如下规定排列

• 1、对于多进去的人全副在最初一排
• 2、前一排的人都比后一排的人矮
• 3、每一行最高的人都在两头地位
• 4、视角从下往上看 (面对着看)，每一行最两头的人开始，先左再右造成非递增序列
• 5、对于有雷同身高的人，依照字典序升序排列

当初要求你输入该排列后果。

算法思路

有两种办法解决该问题，能够间接进行输入，不过地位的计算较为简单并且不易浏览，这里采纳模仿排列的过程来求解。咱们将每一个人的姓名和身高进行绑定并且依照规定进行对立排序 (高个子的在后面)，而后从最初一排往前顺次进行排列 (输入的程序)，排列办法如下：

• 1、首先初始化以后队列 temp，其容量为 m
• 2、应用 index 记录全局队列中待排列的以后人
• 3、填充两头地位 temp[m / 2] = allPeo[index++];
• 4、应用 pointLeft 和 pointRight 别离指向两头地位的左右两边邻近的地位，并应用 count 记录以后曾经填充的人数
• 5、在 count 为奇数的时候填充右边，否则填充左边
• 6、每一行填充结束后输入 temp 并换行。

提交后果

AC 代码

#include <cstdio>
#include <algorithm>
#include <vector>
#include <iostream>

using namespace std;

struct People {
    string name;
    int height{};} people;

vector<People> allPeo;

bool cmp(const People &p1, const People &p2) {return p1.height != p2.height ? p1.height > p2.height : p1.name < p2.name;}

int main() {
    int N, K;
    scanf("%d %d", &N, &K);
    for (int i = 0; i < N; ++i) {
        cin >> people.name >> people.height;
        allPeo.push_back(people);
    }
    sort(allPeo.begin(), allPeo.end(), cmp);
    int eachRowNum = N / K;
    int lastRowNum = eachRowNum + N % K;
    int index = 0;
    // 输入每一行的排列
    for (int i = 0; i < K; ++i) {
        int m = i == 0 ? lastRowNum : eachRowNum;
        vector<People> temp(m);
        int pointLeft = m / 2 - 1;
        int pointRight = m / 2 + 1;
        temp[m / 2] = allPeo[index++];
        int count = 1;
        while (count < m) {if (count % 2 != 0) {temp[pointLeft--] = allPeo[index++];
            } else {temp[pointRight++] = allPeo[index++];
            }
            ++count;
        }
        for (int j = 0; j < temp.size(); ++j) {cout << temp[j].name;
            if (j < temp.size() - 1) cout << " ";
        }
        if (i < K - 1) {cout << endl;}
    }
    return 0;
}