ACM/ICPC 之 用双向链表 or 模拟栈 解“栈混洗”问题-火车调度(TSH OJ - Train)

本篇用双向链表模拟栈混洗过程两种解答方式具体解答“栈混洗”的应用问题

有关栈混洗的定义和解释在此篇:手记-栈与队列相关


列车调度(Train)


描述

某列车调度站的铁道联接结构如Figure 1所示。

其中,A为入口,B为出口,S为中转盲端。所有铁道均为单轨单向式:列车行驶的方向只能是从A到S,再从S到B;另外,不允许超车。因为车厢可在S中驻留,所以它们从B端驶出的次序,可能与从A端驶入的次序不同。不过S的容量有限,同时驻留的车厢不得超过m节。

设某列车由编号依次为{1, 2, ..., n}的n节车厢组成。调度员希望知道,按照以上交通规则,这些车厢能否以{a1, a2, ..., an}的次序,重新排列后从B端驶出。如果可行,应该以怎样

的次序操作?

ACM/ICPC 之 用双向链表 or 模拟栈 解“栈混洗”问题-火车调度(TSH OJ - Train)

输入

共两行。

第一行为两个整数n,m。

第二行为以空格分隔的n个整数,保证为{1, 2, ..., n}的一个排列,表示待判断可行性的驶出序列{a1,a2,...,an}。

输出

若驶出序列可行,则输出操作序列,其中push表示车厢从A进入S,pop表示车厢从S进入B,每个操作占一行。

若不可行,则输出No。

Example 1

Input

5 2
1 2 3 5 4

Output

push
pop
push
pop
push
pop
push
push
pop
pop

Example 2

Input

5 5
3 1 2 4 5

Output

No

限制

1 ≤ n ≤ 1,600,000

0 ≤ m ≤ 1,600,000

时间:2 sec

空间:256 MB


双向链表

  用链表解题的关键其实就在设立一个*P指向A栈顶元素,每一次比对p和p的上一个元素,若能够匹配则删除该元素,并将指针指向该元素的下一个元素,也就是说如果匹配p,则p = p->next,如果匹配p的上一个元素则不动。

  这里的p和p的上一个元素其实就是模拟A栈顶元素和S栈顶元素,这里的时间度为O(n)。

  具体如下:

  

 // 1-n编号车厢按照“栈混洗”从A->S->B,最终确认车厢在B处是否可以按照某一序列排列
// 一种栈结构-输出不要用strcat进行字符链接输出(会TLE)
// 双向链表模拟
// Memory:70984 Time:1753Ms(按最大样例)
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std; #define MAX 1600005 // A->S->B
/*构造双向链表*/
struct Train{
int num;
Train *up;
Train *down;
Train(){};
Train(int n) :num(n){};
}*header,*tailer; //前后哨兵 int target[MAX];
bool output[ * MAX]; //true为push,false为pop
int k; //输出操作数 /*构建*/
void Creat_Train(int n)
{
header = new Train();
header->up = NULL; Train *rear = header; //定义尾针
for (int i = ; i <= n; i++)
{
Train *p = new Train(i); //新链表元素
rear->down = p;
p->up = rear; rear = p;
}
tailer = new Train();
rear->down = tailer;
tailer->up = rear;
tailer->down = NULL;
} /*删除*/
void Delete(Train *p)
{
p->up->down = p->down;
p->down->up = p->up;
delete p;
} int main()
{
int n, m;
scanf("%d%d", &n, &m);
for (int i = ; i <= n; i++) //目标序列
scanf("%d", &target[i]); Creat_Train(n); int counter = ; //S站车厢数量
Train *cur = header->down;
/*开始匹配第i个目标车厢*/
for (int i = ; i <= n; i++)
{
if (cur->num == target[i]) //A栈顶匹配
{
Train *tmp = cur;
cur = cur->down;
Delete(tmp); //删除车厢结点
if (counter + > m) //S滞留车厢过多
{
printf("No\n");
return ;
}
output[k++] = true;
output[k++] = false;
}
else if (cur->up->num == target[i]) //S栈顶匹配
{
Delete(cur->up);
output[k++] = false;
counter--;
}
else{ //A->S
cur = cur->down;
--i;
counter++;
if (cur->down == NULL || counter > m) //A空 Or S滞留车厢过多
{
printf("No\n");
return ;
}
output[k++] = true;
}
}
/*Output*/
for (int i = ; i < k; i++)
{
if (output[i])
printf("push\n");
else printf("pop\n");
} return ;
}

小墨= =原创


模拟栈混洗过程

  也就是设立三个栈,模拟车厢进栈,出栈的过程,时间度也是O(n)。

  TshingHua OJ 中不允许使用STL,所以自己用数组模拟了stack。

  具体如下:

  

 // 1-n编号车厢按照“栈混洗”从A->S->B,最终确认车厢在B处是否可以按照某一序列排列
// 一种栈结构-输出不要用strcat进行字符链接输出(会TLE)
// 模拟栈混洗过程
// Memory:41332 Time:1562Ms(按最大样例)
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std; #define MAX 1600005 // A->S->B
int A[MAX], S[MAX], B[MAX]; //数组模拟栈
int curA, curS; //A和S当前栈顶
bool output[ * MAX]; //true为push,false为pop
int k; //输出操作数 int main()
{
int n, m;
scanf("%d%d", &n, &m);
for (int i = ; i <= n; i++) //目标序列
scanf("%d", &B[i]);
for (int i = n; i >= ; i--) //Init现有序列
A[n - i + ] = i;
curA = n;
curS = ; /*从栈顶开始匹配栈B*/
for (int i = ; i <= n; i++)
{
if (S[curS] == B[i]) //S栈顶匹配
{
curS--; //S出栈
output[k++] = false;
}
else if (A[curA] == B[i]) //A栈顶匹配
{
--curA; //A出栈
output[k++] = true;
output[k++] = false;
if (curS + > m) //S爆栈
{
printf("No\n");
return ;
}
}
else{
S[++curS] = A[curA--]; //A->S(A出栈-S入栈)
output[k++] = true;
i--;
if (!curA || curS > m) //A栈空 or S爆栈
{
printf("No\n");
return ;
}
}
}
/*output*/
for (int i = ; i < k; i++)
{
if (output[i])
printf("push\n");
else printf("pop\n");
} return ;
}

小墨= =原创


上一篇:CF459A Pashmak and Garden (水


下一篇:Linux设置禁止用户登陆