双栈排序(codevs 1170)题解
【问题描述】
Tom最近在研究一个有趣的排序问题。如图所示,通过2个栈S1和S2,Tom希望借助以下4种操作实现将输入序列升序排序。
操作a
如果输入序列不为空,将第一个元素压入栈S1
操作b
如果栈S1不为空,将S1栈顶元素弹出至输出序列
操作c
如果输入序列不为空,将第一个元素压入栈S2
操作d
如果栈S2不为空,将S2栈顶元素弹出至输出序列
如果一个1~n的排列P可以通过一系列操作使得输出序列为1,2,…,(n-1),n,Tom就称P是一个“可双栈排序排列”。例如(1,3,2,4)就是一个“可双栈排序序列”,而(2,3,4,1)不是。下图描述了一个将(1,3,2,4)排序的操作序列:<a,c,c,b,a,d,d,b>
当然,这样的操作序列有可能有几个,对于上例(1,3,2,4),<a,c,c,b,a,d,d,b>是另外一个可行的操作序列。Tom希望知道其中字典序最小的操作序列是什么。
【样例输入1】
4
1 3 2 4
【样例输出1】
a b a a b b a b
【样例输入2】
4
2 3 4 1
【样例输出2】
0
【样例输入3】
3
2 3 1
【样例输出3】
a c a b b d
【解题思路】
本题为NOIP2008提高组第四题,初看觉得这应该是有史以来最水的提高组最后一题了,这不是模拟吗?只不过模拟的东西多了一点而已,然而,当我写着写着,就发现模拟的有点不对劲了……
好吧,这道题的正解应该是图的染色+模拟……
是的,没错,你没有看错,第四题居然要模拟!!!
染色其实是一个深搜的过程,染色是为了区分程序从头到尾始终不能放在一个栈中的数,然后为了保证是字典序最小,因此尽量往栈1中放,如果有始终无法放到同一个栈中的数被放到了同一个栈(这里的被放到同一个栈是指的染成同一种颜色),那么就无解,输出0。(染色的方法可以百度floodfill或者种子染色法)
那么问题来了……挖掘机哪家……不对……怎么区分始终不能放在一个栈中的数呢?
如果存在k使得i<j<k且ak<ai<aj则ai和aj不能进入同一个栈。
我们可以手推一下,如果k>j>i说明,j在i的后面进栈,k在j的后面进栈,而此时ai<aj,那么如果ai和aj进了同一个栈,那么就会是aj先出栈,就肯定不是从小到大排好序的了。
染完色后就好办了,直接模拟进栈出栈的过程……如果是最小值,就出,否则就进,然后因为已经染了色了,根据染的色判断它是进(出)栈1还是栈2,然后输出相应的字符即可。
现在还有一个最最担心的问题,怎么确定这个数是不是当前需要出栈的数(即最小值)?好吧……其实是我眼睛瞎了,是的,我为此纠结了半天,然后看题目……一个1~n的排列P……直接最小值赋值为1,然后出栈了就Inc……
【代码实现】
uses math;
var flag:array[..,..] of boolean;
q1,q2,color,a,f:array[..] of longint;
n,i,j,sum,t1,t2:longint;
procedure dfs(x,c:longint);
var i:longint;
begin
color[x]:=c;
for i:= to n do
if flag[x,i] then
begin
if color[i]=c then
begin
writeln();
halt;
end;
if color[i]= then
dfs(i,-c);
end;
end;
begin
readln(n);
for i:= to n do
read(a[i]);
f[n+]:=maxlongint;
for i:=n downto do
f[i]:=min(a[i],f[i+]);
for i:= to n- do
for j:=i+ to n do
if (a[i]<a[j])and(f[j+]<a[i]) then
begin
flag[i,j]:=true;
flag[j,i]:=true;
end;//初始化,哪些是始终无法进同一个栈的
for i:= to n do
if color[i]= then
dfs(i,);//给每一个数染色
sum:=;
for i:= to n do
begin
if color[i]= then
begin
inc(t1);
q1[t1]:=a[i];
write('a ');
end
else
begin
inc(t2);
q2[t2]:=a[i];
write('c ');
end;
while ((t1<>)and(q1[t1]=sum))or((t2<>)and(q2[t2]=sum)) do
begin
if (<>t1)and(q1[t1]=sum) then
begin
dec(t1);
write('b ');
end
else
begin
dec(t2);
write('d ');
end;
inc(sum);//最小值
end;
end;//最恶心的模拟……
end.
最新文章
- Network服务器
- ZooKeeper系列4:ZooKeeper API简介及编程
- sqlserver常用调优脚本(转)
- Android布局管理器(表格布局)
- Jquery回车键切换焦点方法(兼容各大浏览器)
- Position &; anchorPoint 深入
- MySQL中的一些内置函数
- idea配置svn
- localhost访问不了的解决方法
- mxGraph进阶(一)mxGraph教程-开发入门指南
- spring boot 打包war
- 《SpringMVC从入门到放肆》十一、SpringMVC注解式开发处理器方法返回值
- 最长(大)回文串的查找(字符串中找出最长的回文串)PHP实现
- 日志切割工具logrotate解决Tomcat catalina.out日志过大的问题
- MOT南京站 | 卓越研发之路:锻造顶级后端系统
- git在本地回退
- Linux源码解析-内核栈与thread_info结构详解
- iBatis.Net 配置 SQL语句执行 日志
- Delphi中记录体做为属性的赋值方法
- numpy二分查找
热门文章
- JavaScript学习笔记---入门
- python连接hiveserver2
- 用了skin皮肤控件之后,报错:容量超出了最大容量 参数名:capacity
- ASP.Net软件工程师基础(一)
- 前端开发 Grunt 之 Connect
- xcode7.3 升级 xcode8.0 后权限设置问题(升级xcode 8.0 后构建版本不显示问题)
- leetcode题目总结(转)
- THE ONE THING PEOPLE WILL MASSIVELY OVERPAY FOR (有一个东西人们是愿意出高价购买的)
- 【LeetCode】19. Remove Nth Node From End of List
- JS判断手机浏览器