// 未精简全AC代码
// Bob175 Tom 188 Joe 190 Nick186
// Ann168 Mike170 Eva 168
// Tim160 Amy 160 John159
#include <bits/stdc++.h>
using namespace std;
struct Stu{
string name;
int height;
bool operator < (Stu a) const{
// 不相等按身高非递减序
if(height != a.height)
return height > a.height;
// 否则返回名字升序
return name < a.name;
}
};
void print(vector<Stu>& output){
int first = 0;
for(auto o : output)
cout << (first++ ? " " : "") << o.name;
cout << endl;
// 输出完清空元素输出下一排
output.clear();
}
int main() {
// 读取总人数N人总排数K排
int n, k;
set<Stu> stu;
vector<Stu> output;
cin >> n >> k;
// 读取名字 身高
for(int i = 0; i < n; i++) {
string name; int height;
cin >> name >> height;
stu.insert({name, height});
}
// 算出最后一排多出来的人数
int last = n - n / k * k, flag = 1;
// 第一排要塞多出来的人数
auto s = begin(stu);
for(int i = 0; i < n / k + last; i++, s++){
// 中间到两旁非增序 从中间先左后右交替入队(反过来
// 第一个直接推入 并到处理下一个
if(i == 0) {
output.push_back(*s);
continue;
}
// flag = 1 插入左边 flag = 0 插入右边
if(flag == 1){
flag = 0;
output.insert(begin(output), *s);
}
else{
flag = 1;
output.push_back(*s);
}
}
// 排完一队直接输出
print(output);
// 输出剩余排 k - 1 重置flag
for(int j = 0; j < k - 1; j++){
flag = 1;
for(int i = 0; i < n / k; i++, s++){
// 中间到两旁非增序 从中间先左后右交替入队(反过来
// 第一个直接推入 并到处理下一个
if(i == 0) {
output.push_back(*s);
continue;
}
// flag = 1 插入左边 flag = 0 插入右边
if(flag == 1){
flag = 0;
output.insert(begin(output), *s);
}
else{
flag = 1;
output.push_back(*s);
}
}
print(output);
}
}
// 精简版 又试了试传递容器引用
#include <bits/stdc++.h>
using namespace std;
struct Stu{
string name;
int height;
bool operator < (Stu a) const{
// 不相等按身高非递减序
if(height != a.height)
return height > a.height;
// 否则返回名字升序
return name < a.name;
}
};
void print(vector<Stu>& output){
int first = 0;
for(auto o : output)
cout << (first++ ? " " : "") << o.name;
cout << endl;
}
void queueUp(auto& s, int peo){
vector<Stu> output;
for(int i = 0, flag = 1; i < peo; i++, s++){
// 中间到两旁非增序 从中间先左后右交替入队(反过来
// 第一个直接推入 并到处理下一个
if(i == 0) {
output.push_back(*s);
continue;
}
// flag = 1 插入左边 flag = 0 插入右边
if(flag == 1){
flag = 0;
output.insert(begin(output), *s);
}
else{
flag = 1;
output.push_back(*s);
}
}
// 排完一队直接输出
print(output);
}
int main() {
// 读取总人数N人总排数K排
int n, k;
set<Stu> stu;
vector<Stu> output;
cin >> n >> k;
// 读取名字 身高
for(int i = 0; i < n; i++) {
string name; int height;
cin >> name >> height;
stu.insert({name, height});
}
// 算出最后一排多出来的人数
int last = n - n / k * k;
// 第一排要塞多出来的人数
auto s = begin(stu);
queueUp(s, n / k + last);
// 输出剩余排 k - 1 重置flag
for(int j = 0; j < k - 1; j++){
queueUp(s, n / k);
}
}
// Bob175 Tom 188 Joe 190 Nick186
// Ann168 Mike170 Eva 168
// Tim160 Amy 160 John159
代码开头有这个东西，这是当时用来思考排列出来的效果是怎么样的。因为当时不知道到底是按照什么方式排序身高以及这些人在每一排里面的位置。
通过这样具体的模拟一下，标记每一个人的数据，就能够更直观看到题目需要实现的规律是什么。虽然花了点时间，但是对于整个解题来讲还是很重要的。
就像常常说道理解题意很重要，这里显然也是这么回事。以后可以多多尝试这样的理解方式。
发现如果不想写什么函数传参的类型，直接给一个 auto 让编译器自己推导就可以了，我们只需要负责将东西传进去。如果要对内容进行更改而不是赋一份拷贝的话，那就加一个 & 即可。像下面的精简版传递容器引用的时候，就在函数参数类型写了一个 auto & 。
operator const ，当时重载 set 的自定义排序的时候不太记得怎么写，所以报了个错误。搜了下原来是忘了一个 const 常量关键字。放在参数类型的小括号 （） const 后面即可。
还有就是虽然 devc++ 上如果你不写 bool 的函数类型可以通过编译检测，并且还可以正确输出。但 PAT 上不写就直接编译报错了。不知道什么原理，有什么区别。
好像 lambda 函数写的时候是可以根据返回值类型来推导函数类型的，不知道这个重载的是否也有这样特性。
这里用到了前几题奇偶位置时候的交替输出，设一个 flag 输出一次改为 1 到另外的判断又改为 0。
因为这里涉及到两头插入，所以用了一个 vector 的 insert()，向容器任意位置插入元素，这里就是首尾。push_back() 跟 output.insert(end(output), *s) 的效果是一样的。
而这里输入的位置不是下标，而是地址的位置。
除了用 vector 向量以外还有另外一个容器是，deque 双端队列。它的函数就是 push_back() 和 push_front()。省去自己写地址了。
未精简之前因为没有采用函数，所以 vector 是共用的，但是每一行都需要重新排队，所以需要清理前一排的内容，用到了 clear() 清除函数。
是 clear 而不是 clean，当时就写错了。
原文：https://www.cnblogs.com/Atl212/p/15222598.html