UC知道Pascal汽车拉力赛
来源：百度知道 编辑：UC知道 时间：2024/06/17 15:38:07
问题描述：
一种汽车拉力赛将在如下所示的一个赛道中进行。
从入口（entrance）到达起点(starting line)只有唯一窄长通道，于是赛车必须在起跑线后排起队，假设它们的顺序是根据预赛成绩来确定。赛车到达入口时是以某种顺序的，我们现在想知道是否有办法将这些赛车按它们的编号从小到大重新排列。重新排列是通过一个支路(Bypass)进行的。注意赛车只能按图中箭号方法前进，同时，在支路中赛车也必须排队前进，因为支路一条窄长通道，可以假设支路是足够长的，足以容纳所有参与比赛的车辆。
例如，假设有4辆赛车，它们到达入口时的顺序是1, 3, 2, 4，我们可以通过以下方案重新排列这4辆车，使之到达起点时的顺序是1,2,3,4。
＃1车到达起点
＃3车进入支路，等待＃2车
＃2车到达起点
＃3车从支路到起点
＃4到达起点
输入文件（RALLY.IN）：
输入文件包含多个测试数据。输入文件的第一行包含一个整数，表示测试数据的数目。每一种数据的第一行为整数N，表示参赛赛车的数目，下一行是一个1--N的排列，表示N辆赛车在入口处的排列顺序，两个赛车编号之间有一个空格，N小于100。
输出文件（RALLY.OUT）：
对于每一组数据，输出一行。如果测试数据表示的顺序可以重新排列则输出 "YES" ，否则输出"NO" 。
输入输出样例：
RALLY.IN
2
4
1 3 2 4
3
3 2 1
RALLY.OUT
YES
NO
问题补充：1
一种汽车拉力赛将在如下所示的一个赛道中进行。
从入口（entrance）到达起点(starting line)只有唯一窄长通道，于是赛车必须在起跑线后排起队，假设它们的顺序是根据预赛成绩来确定。赛车到达入口时是以某种顺序的，我们现在想知道是否有办法将这些赛车按它们的编号从小到大重新排列。重新排列是通过一个支路(Bypass)进行的。注意赛车只能按图中箭号方法前进，同时，在支路中赛车也必须排队前进，因为支路一条窄长通道，可以假设支路是足够长的，足以容纳所有参与比赛的车辆。
例如，假设有4辆赛车，它们到达入口时的顺序是1, 3, 2, 4，我们可以通过以下方案重新排列这4辆车，使之到达起点时的顺序是1,2,3,4。
＃1车到达起点
＃3车进入支路，等待＃2车
＃2车到达起点
＃3车从支路到起点
＃4到达起点
输入文件（RALLY.IN）：
输入文件包含多个测试数据。输入文件的第一行包含一个整数，表示测试数据的数目。每一种数据的第一行为整数N，表示参赛赛车的数目，下一行是一个1--N的排列，表示N辆赛车在入口处的排列顺序，两个赛车编号之间有一个空格，N小于100。
输出文件（RALLY.OUT）：
对于每一组数据，输出一行。如果测试数据表示的顺序可以重新排列则输出 "YES" ，否则输出"NO" 。
输入输出样例：
RALLY.IN
2
4
1 3 2 4
3
3 2 1
RALLY.OUT
YES
NO
问题补充：1
很简单的题目呢，就是一个栈啊～你现在弄两个栈，一个栈是排队的车，还有一个栈是支路上的车
举例说明，1324
step1：排队的车是1324，支路上的车是空。
取排队车的第一个1，而结束的队列第一个也是1，于是1不用到支路，直接出队，现在排队的车是324，而支路上的车还是空。
step2：排队车第一个是3，而结束队列应该是2在3前面，于是3出队，进入支路车，现在排队的车是24，而支路上的车是3
step3：同step1，现在排队的车是4，支路上的车是3
step4：排队车是4，但是结束的是3，比4小，我们在支路上找，第一个是不是3（如果不是说明就要输出no了），是，让3出队，支路上的车是4
step5：4也出队，完成～
再比如321，3必须先进支路，然后2也必须进支路，1出队；然后应该是2，但是支路上第一个是3，不行，输出no
栈就是先进先出的一种数据结构，可以用数组实现。完成后建议你看一下2008noip一题，是这题的进化版，有两个支路，做法就不一样了
program;
begin
write('I don't know');
readln;
end.