C++/PTA 对称排序

简介: 你供职于由一群丑星作为台柱子的信天翁马戏团。你刚完成了一个程序编写,它按明星们姓名字符串的长度非降序(即当前姓名的长度至少与前一个姓名长度一样)顺序输出他们的名单。然而,你的老板不喜欢这种输出格式

题目要求

你供职于由一群丑星作为台柱子的信天翁马戏团。你刚完成了一个程序编写,它按明星们姓名字符串的长度非降序(即当前姓名的长度至少与前一个姓名长度一样)顺序输出他们的名单。然而,你的老板不喜欢这种输出格式,提议输出的首、尾名字长度较短,而中间部分长度稍长,显得有对称性。老板说的具体办法是对已按长度排好序的名单逐对处理,将前者放于当前序列的首部,后者放在尾部。如输入样例中的第一个案例,Bo和Pat是首对名字,Jean和Kevin是第二对,余此类推。

输入格式:


输入包含若干个测试案例。每个案例的第一行含一个整数n(n>=1),表示名字串个数。接下来n行每行为一个名字串,这些串是按长度排列的。名字串中不包含空格,每个串至少包含一个字符。n=0为输入结束的标志。

输出格式:


对每一个测试案例,先输出一行“Set n”,其中n从1开始取值,表示案例序号。接着是n行名字输出,如输出样例所示。


输入样例:

7

Bo

Pat

Jean

Kevin

Claude

William

Marybeth

6

Jim

Ben

Zoe

Joey

Frederick

Annabelle

5

John

Bill

Fran

Stan

Cece

0


输出样例:

SET 1

Bo

Jean

Claude

Marybeth

William

Kevin

Pat

SET 2

Jim

Zoe

Frederick

Annabelle

Joey

Ben

SET 3

John

Fran

Cece

Stan

Bill


解题思路

输入名字并存入栈中。

将名字交替存入队列头部和尾部,并输出最终结果。

代码

#include <iostream>
#include <string>
#include <deque>
#include <stack>
using namespace std;
int main() {
    deque<string> s; // 使用双端队列来存储名字
    stack<string> swop; // 存放所有名字的栈
    int count = 1; // 计数器,用于输出 SET X 的 X
    int sum;
    while (cin >> sum && sum != 0) { // 循环读入每组数据
        for (int i = 0; i < sum; i++) {
            string name;
            cin >> name; // 读入每个名字
            swop.push(name); // 将名字存入栈中
        }
        if (sum % 2 == 0) { // 名字数为偶数时
            for (int j = 0; j < sum; j++) {
                if (j % 2 == 0) {
                    s.push_back(swop.top()); // 交替存入队列尾部
                } else {
                    s.push_front(swop.top()); // 交替存入队列头部
                }
                swop.pop(); // 将使用过的名字出栈
            }
        } else { // 名字数为奇数时
            for (int j = 0; j < sum; j++) {
                if (j % 2 == 0) {
                    s.push_front(swop.top()); // 交替存入队列头部
                } else {
                    s.push_back(swop.top()); // 交替存入队列尾部
                }
                swop.pop(); // 将使用过的名字出栈
            }
        }
        cout << "SET " << count << endl; // 输出 SET X
        for (int j = 0; j < sum; j++) {
            cout << s.front() << endl; // 输出队列头部的名字
            s.pop_front(); // 弹出队列头部的名字
        }
        count++;
    }
    return 0;
}

头文件

<string>:定义了字符串类型和相关的操作函数。在代码中,使用该头文件定义了变量 name 来存储每个输入的名字。

<deque>:定义了双端队列容器。在代码中,使用该头文件定义了双端队列 s 用于存储名字。

<stack>:定义了栈容器。在代码中,使用该头文件定义了栈 swop 用于存放所有名字。


栈(stack)是一种“后进先出”(LIFO)的数据结构,即最后压入栈的元素最先出栈。


在这段代码中,使用了一个栈 swop,用于存放所有输入的名字。每输入一个名字,就将其压入栈中。在接下来的处理过程中,将从栈中弹出名字并进行操作,直到栈中没有元素为止。因此,栈在这里起到了缓存输入数据的作用,使整个处理过程更为高效。


总结

本文基于swop数据结构栈进行解题,读者可自行消化。

我是秋说,我们下次见。

目录
相关文章
|
5月前
|
存储 C++
【PTA】L1-039 古风排版(C++)
【PTA】L1-039 古风排版(C++)
30 1
|
6月前
|
Java C++
部落(pta)(并查集) Java以及C++
部落(pta)(并查集) Java以及C++
49 2
|
5月前
|
C++ 容器
C++之deque容器(构造、赋值、大小、插入与删除、存取、排序)
C++之deque容器(构造、赋值、大小、插入与删除、存取、排序)
|
5月前
|
存储 人工智能 C++
【PTA】L1-064 估值一亿的AI核心代码(详C++)
【PTA】L1-064 估值一亿的AI核心代码(详C++)
35 1
|
5月前
|
存储 C++ 索引
【PTA】L1-059 敲笨钟(C++)
【PTA】L1-059 敲笨钟(C++)
26 1
|
5月前
|
存储 人工智能 C++
【PTA】L1-093 猜帽子游戏(C++)
【PTA】L1-093 猜帽子游戏(C++)
85 1
|
5月前
|
C++
【PTA】L1-046 整除光棍(C++)
【PTA】L1-046 整除光棍(C++)
44 1
|
5月前
|
存储 C++
【PTA】L1-043 阅览室(C++)
【PTA】L1-043 阅览室(C++)
31 1
|
5月前
|
算法 搜索推荐 C++
C++之STL常用算法(遍历、查找、排序、拷贝、替换、算数生成、集合)
C++之STL常用算法(遍历、查找、排序、拷贝、替换、算数生成、集合)
|
6月前
|
人工智能 C++
c++实现 离散数学 “自反 对称 ” 详解
c++实现 离散数学 “自反 对称 ” 详解