简单的数据结构_via牛客网
2024-10-20 16:39:25
题面
链接:https://ac.nowcoder.com/acm/contest/28537/K
来源:牛客网时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 131072K,其他语言262144K
64bit IO Format: %lld题目描述
栗酱有一天在网上冲浪的时候发现了一道很有意思的数据结构题。
该数据结构形如长条形。
一开始该容器为空,有以下七种操作。
1 a从前面插入元素a
2 从前面删除一个元素
3 a从后面插入一个元素
4 从后面删除一个元素
5 将整个容器头尾翻转
6 输出个数和所有元素
7 对所有元素进行从小到大排序
输入描述:
只有一组数据,第一行n≤50000,m≤200000, a≤100000 代表最大数据数目和操作次数。
接下来每一行一个操作如上描述。保证所有操作合法(不会在容器为空时删除元素)。
6、7操作共计不会超过10次。
输出描述:
当执行6操作时,第一行先输出当前的个数,然后从头到尾按顺序输出,每两个元素之间用一个空格隔开,末尾不能有空格。
示例1
输入
10 9
1 1
3 5
3 4
6
4
5
6
7
6
输出
3
1 5 4
2
5 1
2
1 5
题解
这道题目可以使用STL中的双端队列deque
注意: 题目说有一个操作可以调转容器,实际上并不需要,
使用反迭代器以及flags标记是否调转.
代码
#include <iostream>
#include <deque>
#include <algorithm>
using namespace std;
deque<int>a;
int main()
{
bool flags = true;//正常顺序的标志
int max_num, T;
cin >> max_num >> T;
while (T--)
{
deque<int>::iterator it;
deque<int>::reverse_iterator r_it;
int data;
int op;
cin >> op;
switch (op)
{
case 1:
cin >> data;
if (flags)
{
a.push_front(data);
}
else
{
a.push_back(data);
}
break;
case 2:
if (flags)
{
a.pop_front();
}
else
{
a.pop_back();
}
break;
case 3:
cin >> data;
if (flags)
{
a.push_back(data);
}
else
{
a.push_front(data);
}
break;
case 4:
if (flags)
{
a.pop_back();
}
else
{
a.pop_front();
}
break;
case 5:
if (flags)
{
flags = false;
}
else
{
flags = true;
}
break;
case 6:
cout << a.size() << endl;
if (flags)
{
for (it = a.begin(); it != a.end(); it++)
cout << *it << ' ';
}
else
{
for (r_it = a.rbegin(); r_it != a.rend(); r_it++ )
cout << *r_it << ' ';
}
cout << endl;
break;
case 7:
if (flags)
{
sort(a.begin(), a.end());
}
else
{
sort(a.rbegin(), a.rend());
}
break;
}
}
return 0;
}
最新文章
- 【腾讯Bugly干货分享】微信iOS SQLite源码优化实践
- 30多条mysql数据库优化方法,千万级数据库记录查询轻松解决(转载)
- 一个N*M的矩阵,找出这个矩阵中所有元素的和不小于K的面积最小的子矩阵
- php常用函数file
- java连接数据源-读取tomcat数据源配置
- extjs 2.0获取选中的radio的值
- 【服务器环境搭建-Centos】常用系统命令篇
- [转载]js中__proto__和prototype的区别和关系
- Linux下tomcat使用
- mapreduce框架详解【转载】
- Mysql数据库里面的String类型依照数字来排序以及按时间排序的sql语句
- 一个想法照进现实-《IT连》创业项目:创业时该不该用新手程序员
- Opengl4.5 中文手册—A
- mongodb副本集搭建过程中的问题和解决技巧
- iframe父页面获取子页面的参数
- 利用并查集+贪心解决 Hdu1232
- 从 TFS 迁移源代码到 git
- 51nod 1412 AVL树的种类(经典dp)
- JQuery返回Json日期格式的問題
- Spring-IOC bean 生命周期之 Lifecycle 钩子