美业网站,最近新闻热点国家大事,商城购物网站开发意义,百度手机点击排名工具有一个火车站#xff0c;铁轨铺设如图6-1所示。有n节车厢从A方向驶入车站#xff0c;按进站顺序编号为1#xff5e;n。你的任务是判断是否能让它们按照某种特定的顺序进入B方向的铁轨并驶出车站。例如#xff0c;出栈顺序(5 4 1 2 3)是不可能的#xff0c;但(5 4 3 2 1)是…有一个火车站铁轨铺设如图6-1所示。有n节车厢从A方向驶入车站按进站顺序编号为1n。你的任务是判断是否能让它们按照某种特定的顺序进入B方向的铁轨并驶出车站。例如出栈顺序(5 4 1 2 3)是不可能的但(5 4 3 2 1)是可能的。
为了重组车厢你可以借助中转站C。这是一个可以停放任意多节车厢的车站但由于末端封顶驶入C的车厢必须按照相反的顺序驶出C。对于每个车厢一旦从A移入C就不能再回到A了一旦从C移入B就不能回到C了。换句话说在任意时刻只有两种选择A→C和C→B。 【分析】 在中转站C中车厢符合后进先出的原则因此是一个栈。
样例 输入
5
5 4 3 2 1输出
yes解法
use std::{collections::VecDeque, io};fn main() {let mut buf String::new();io::stdin().read_line(mut buf).unwrap();let n: usize buf.trim().parse().unwrap();let mut source VecDeque::from((1..n).collect::Vec_());let mut buf String::new();io::stdin().read_line(mut buf).unwrap();let target: Vecusize buf.split_whitespace().map(|x| x.parse().unwrap()).collect();let mut b 0;let mut s: VecDequeusize VecDeque::new();while b n {if !source.is_empty() *source.front().unwrap() target[b] {source.pop_front();b 1;} else if !s.is_empty() *s.back().unwrap() target[b] {s.pop_back();b 1;} else if !source.is_empty() {s.push_back(source.pop_front().unwrap());} else {break;}}if b n {println!(yes);} else {println!(no);}
}
