当前位置：首页 > news >正文

刷题记录:NC146615简单的数据结构

news 来源：原创 2024/5/17 18:57:35

传送门:牛客

题目描述;

栗酱有一天在网上冲浪的时候发现了一道很有意思的数据结构题。
该数据结构形如长条形。
一开始该容器为空，有以下七种操作。
1 a从前面插入元素a
2 从前面删除一个元素
3 a从后面插入一个元素
4 从后面删除一个元素
5 将整个容器头尾翻转
6 输出个数和所有元素
7 对所有元素进行从小到大排序
输入:
10 9
1 1
3 5
3 4
6
4
5
6
7
6
输出:
3
1 5 4
2
5 1
2
1 5

MD,刚开始看到这道题居然忘记了双向队列这个STL,害我只能手写了一个双向队列,搞完之后才想起来,只能用手写双向队列比较快来安慰我自己了(上方为STL,下方为手写).

在这里插入图片描述
首先是手写双向队列部分,因为我们知道了我们的序列的长度,我们完全可以开两倍的内存保证N前面的部分来存储前半部分数据,N后面的来存储后半部分的数据,此时我们还需要两个指针分别来指向左边和右边的边界

对于每一次的增减操作前我们都需要考虑翻转的问题,既然已经手写双向队列了,我们就来个优化,不直接reverse,而是采用平衡树中的一种打标记的操作来记录我们有没有进行翻转(注意只有一个数,或者没有数的时候不能打标记)

对于操作1,假设没有翻转.直接左指针往左移即可,反之则移动右指针

对于操作2,根据有没有翻转来决定左右指针移动

对于操作3,4,都与上同理

对于操作5,我们进行打标记操作,注意两次翻转等于没有翻转

对于操作6,我们直接对[L,R]区间内的数据进行排序即可

注意实现过程中的小细节即可

下面是手写优先队列的具体代码:

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string.h>
#include <stack>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x = 0, w = 1;
	char ch = getchar();
	for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') w = -1;
	for (; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
	return x * w;
}
#define maxn 1000000
#define ll_maxn 0x3f3f3f3f3f3f3f3f
const double eps = 1e-8;
int a[1000002];
int main() {
	int n, m;
	n = read();
	m = read();
	int opt;
	int l = n + 500, r = n + 500;
	int flag = 1;
	for (int i = 1; i <= m; i++) {
		opt = read();
		if (opt == 1) {
			int num;
			num = read();
			if (flag == 1) {
				a[--l] = num;
			} else {
				a[r++] = num;
			}
		} else if (opt == 2) {
			if (flag == 1) {
				l++;
			} else {
				r--;
			}
		} else if (opt == 3) {
			int num;
			num = read();
			if (flag == 1) {
				a[r++] = num;
			} else {
				a[--l] = num;
			}
		} else if (opt == 4) {
			if (flag == 1) {
				r--;
			} else {
				l++;
			}
		} else if (opt == 5) {
			if(r-l>1) flag = 1 - flag;
		} else if (opt == 6) {
			printf("%d\n", r - l);
			if (flag == 1) {
				for (int i = l; i <= r - 1; i++) {
					if (i != r - 1) printf("%d ", a[i]);
					else printf("%d\n", a[i]);
				}
			} else {
				for (int i = r - 1; i >= l; i--) {
					if(i!=l) printf("%d ", a[i]);
					else printf("%d\n",a[i]);
				}
			}
		} else if (opt == 7) {
			sort(a + l, a + r);
			flag = 1;
		}
	}
	return 0;
}

emmm,似乎我们的手写双向队列实现起来码量有点大

对于我们的STL来说,解决这个问题就比较轻松了

对于从队头队尾插入删除元素，我们可以用STL中的deque（双端队列）便于操作这些是deque的一些基本操作：

push_back(x)/push_front(x) //把x压入后/前端

back()/front() //访问(不删除)后/前端元素

pop_back() pop_front() //删除后/前端元素

empty() //判断deque是否空

size() //返回deque的元素数量

clear() //清空deque

支持通过sort(d.begin(),d.end())进行排序,也支持通过reverse函数进行翻转操作。

然后就直接使用STL函数尽情的乱杀这道题即可

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string.h>
#include <stack>
#include <deque>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000000
#define ll_maxn 0x3f3f3f3f3f3f3f3f
const double eps=1e-8;
deque<int>q;//双向队列
int main() {
	int n,m;n=read();m=read();
	while(m--) {
		int opt;opt=read();
		if(opt==1) {
			int num;num=read();
			q.push_front(num);
		}
		else if(opt==2) {
			q.pop_front();
		}
		else if(opt==3) {
			int num;num=read();
			q.push_back(num);
		}
		else if(opt==4) {
			q.pop_back();
		}
		else if(opt==5) {
			reverse(q.begin(),q.end());
		}
		else if(opt==6) {
			cout<<q.size()<<endl;
			for(int i=0;i<q.size();i++) cout<<q[i]<<" ";
			cout<<endl;
		}
		else sort(q.begin(),q.end());
	}
	return 0;
}