【NOIP2008】双栈排序

本来天真地以为是个模拟:怎么这一年都是两分钟写完的水题

然后发现错了

于是听说有这么个规律:若存在i<j<k且a[k]<a[i]<a[j]则i和j不能被加入同一个栈

这个也很好理解:若两个数,小的先加入某个栈,大的也要加入那个栈,那么小的肯定要先出栈;那么小的出栈就要保证比这个数小的数已经全部出栈了;则若存在一个比它更小的数还没有入栈那么这个数肯定还不能出栈。。大的那个数也就不能进入了。

知道了每个数要进入哪个栈然后再模拟就可以了233

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz