文章
10
粉丝
66
获赞
3
访问
45.3k
解析:
题目大意:一个队列,只能从一端插入数据,但可以从两端删除数据。现在给定一段数据互不相同的插入序列,然后给一些删除序列,判断这些删除顺序的可行性。
用两个指针pi与pj分别指向插入序列insertion与删除序列deletion。pi初始指向0,表示第一个数据待插入。每读到一个待删除数据时,有以下情况:
1、当前待删除数据等于待插入数据,把数据进队列然后马上出队列就可以了(相当于什么也不做),然后pi右移,表示下一个数据待插入;
2、当前待删除数据不等于待插入数据,且待删除数据还没有插入,那就一口气把待删除数据之前未插入的数据都插入;
3、当前待删除数据不等于待插入数据,且待删除数据已经插入了,那就检查队列两端是不是待删除数据,不是就意味着这个数无法删除,该删除序列无法实现。
数据结构上,可以用deque,它的用法类似于vector,但是支持时间复杂度为O(1)的两端插入删除操作。
#include <deque>
#include <unordered_set>
#include <iostream>
using namespace std;
void test () {
int N, K;
int i, j;
scanf("%d %d", &N, &K);
deque<int> insertion(N);
for (i = 0; i < N; i++) scanf("%d", &insertion[i]);
for (int k = 0; k < K; k++) {
unordered_set<int> inserted;
deque<int> deletion(N), q;
for (j = 0; j < N; j++) scanf("%d", &deletion[j]);
for (j = 0, i = 0; j < N; j++) {
if (deletion[j] == insertion[i]) {
...
登录后发布评论
暂无评论,来抢沙发