当前位置 博文首页 > Aaron_Yang：PAT 7-4 毕业照 (双向队列法)
照毕业照一定要排好队，不然就会有人被挡住，造成终身遗憾。假设有N个毕业生，准备排K行，拍毕业照的摄影师定下这么几条规矩： 1、每一行的人数一定是N/K个，如果有多的同学，全部站最后一排； 2、后排的一定不能比前排任何一个同学矮； 3、在任意一排，个子最高的站中间，之后次高的站他的右边，第三高的站他的左边，第四高的又站右边，这样依次轮换。例如，有5个同学，身高依次是190厘米，188厘米，186厘米，175厘米和170厘米，那么最后应该排成175，188, 190，186， 170。这里我们假设摄影师面向同学们站立，这样摄影师的左手就是同学们的右手。 4、如果身高相同，那就按姓名的字母序的升序排列，我们假定没有重名的。
每个输入包括一个测试用例，第一行有两个正整数N和K，其中N是毕业生总数，K是排数。 N<=10000，K<=10，随后N行，分别给出不超过8个字符的姓名以及他们的身高，姓名中不含空格。
对每一组输入，显示出毕业生拍照时的位置情况，要求打印K行学生的姓名，姓名之间以1个空格分隔，行尾不得有多余空格。因为你是面向毕业生的，所以在最后一排的同学应该显示在第一行，在第一排的同学显示在最后一行。
在这里给出一组输入。例如：
10 3
Tom 188
Mike 170
Eva 168
Tim 160
Joe 190
Ann 168
Bob 175
Nick 186
Amy 160
John 159
在这里给出相应的输出。例如：
Bob Tom Joe Nick
Ann Mike Eva
Tim Amy John
#include<iostream>
#include<vector>
#include<deque>
#include<algorithm>
using namespace std;
struct person
{
string name;
int height;
person() {}
person(string str, int h) :name(str), height(h) {}
};
bool cmp(person p1, person p2)
{
if (p1.height == p2.height)
return p1.name < p2.name;
return p1.height > p2.height;
}
void printing(int first, int number, deque<string> que, deque<string>& que2)
{
//三个数 1 0 2
//四个数 3 1 0 2
int count = 0;
for (int i = first; count < number; i++, count++)
{
if (count % 2 == 0)
que2.push_back(que[i]);
else
que2.push_front(que[i]);
}
for (int i = 0; i < que2.size() - 1; i++)
cout << que2[i] << " ";
cout << que2[que2.size() - 1] << endl;
que2.clear();
}
int main()
{
int n, k;
cin >> n >> k;
person* stu = new person[n + 1];
for (int i = 0; i < n; i++)
{
string str; int h;
cin >> str >> h;
stu[i].name = str;
stu[i].height = h;
}
//排序
sort(stu, stu + n, cmp);
deque<string>deq1, deq2;
for (int i = 0; i < n; i++)
{
//倒序输入
deq1.push_back(stu[i].name);
}
//每行人数
int per_line_num = n / k;
//第一排
int n1 = n - per_line_num * (k - 1);
printing(0, n1, deq1, deq2);
//k排
for (int i = 1; i < k; i++)
{
int first_num = n1 + per_line_num * (i - 1);
printing(first_num, per_line_num, deq1, deq2);
}
return 0;
}
