Train
所属分类：C#编程
开发工具：Visual C++
文件大小：1106KB
下载次数：1
上传日期：2019-04-21 16:52:13
上 传 者：
湘伦
说明： 某列车调度站的铁道联接结构如图所示。
其中，A为入口，B为出口，S为中转盲端。所有铁道均为单轨单向式：列车行驶的方向只能是从A到S，再从S到B；也可以不在S中驻留，直接从A驶向B；另外，不允许超车。因为车厢可在S中驻留，所以它们从B端驶出的次序，可能与从A端驶入的次序不同。不过S的容量有限，同时驻留的车厢不得超过m节。
设某列车由编号依次为{a1, a2, ..., an}的n节车厢组成。调度员希望知道，按照以上交通规则，这些车厢能否以{1, 2, ..., n}的次序，重新排列后从B端驶出。
(In this station, A is the entrance for each train and B is the exit. S is the transfer end. All single tracks are one-way, which means that the train can enter the station from A to S, and pull out from S to B. Note that the overtaking is not allowed. Because the compartments can reside in S, the order that they pull out at B may differ from that they enter at A. However, because of the limited capacity of S, no more that m compartments can reside at S simultaneously.
Assume that a train consist of n compartments labeled {1, 2, , n}. A dispatcher wants to know whether these compartments can pull out at B in the order of {a1, a2, , an} (a sequence). If can, in what order he should operate it?)
文件列表:
.vs\Project1\v16\.suo (34304, 2019-04-21)
.vs\Project1\v16\Browse.VC.db (1576960, 2019-04-21)
.vs\Project1\v16\ipch\AutoPCH\a8089b478df9616\Դ.ipch (2424832, 2019-04-21)
.vs\Project1\v16\ipch\AutoPCH\d22f942b75d6640f\239D217D4F1AF1F7650BC499ABF7ED5391C46AFA.ipch (2359296, 2019-04-21)
Debug\Project1.exe (45056, 2019-04-21)
Debug\Project1.ilk (350472, 2019-04-21)
Debug\Project1.log (103, 2019-04-21)
Debug\Project1.pdb (569344, 2019-04-21)
Debug\Project1.tlog\CL.command.1.tlog (596, 2019-04-21)
Debug\Project1.tlog\CL.read.1.tlog (2396, 2019-04-21)
Debug\Project1.tlog\CL.write.1.tlog (376, 2019-04-21)
Debug\Project1.tlog\link.command.1.tlog (1122, 2019-04-21)
Debug\Project1.tlog\link.read.1.tlog (2538, 2019-04-21)
Debug\Project1.tlog\link.write.1.tlog (414, 2019-04-21)
Debug\Project1.tlog\Project1.lastbuildstate (214, 2019-04-21)
Debug\vc142.idb (35840, 2019-04-21)
Debug\vc142.pdb (77824, 2019-04-21)
Debug\Դ.obj (12066, 2019-04-21)
Project1.sln (1436, 2019-04-21)
Project1.vcxproj (6119, 2019-04-21)
Project1.vcxproj.filters (948, 2019-04-21)
Project1.vcxproj.user (168, 2019-04-21)
Դ.cpp (1375, 2019-04-21)
.vs\Project1\v16\ipch\AutoPCH\a8089b478df9616 (0, 2019-04-21)
.vs\Project1\v16\ipch\AutoPCH\d22f942b75d6640f (0, 2019-04-21)
.vs\Project1\v16\ipch\AutoPCH (0, 2019-04-21)
.vs\Project1\v16\ipch (0, 2019-04-21)
.vs\Project1\v16 (0, 2019-04-21)
.vs\Project1 (0, 2019-04-21)
Debug\Project1.tlog (0, 2019-04-21)
.vs (0, 2019-04-21)
Debug (0, 2019-04-21)
A.后驶入S区的车厢要先出来，相当于堆栈Stack的作用，用一个数组来进行模拟。当车厢编号与所需序列不符时就进入S区存着，一旦发现有车厢编号与所需序列相符，先将其直接从A开到B，此时所需序列变化，再从高到低从S区中检索将相应车厢驶出。如果在过程中S区车厢超过了容量，或者所有车厢都经过一次检查后S区中还有剩余车厢，就说明该序列实现1~n的顺序重组不可行。
B.除了一些简单的debug问题，只遇到过一次困扰但也很快解决。第一次编译成功的交上的代码是45分，只有第一个数据是wrong answer，其余都是accept，显然这不是算法的问题，是某个细节出了错。检查后发现是在判断S区容量时出了错，其实我设定的top相当于栈内最高元素的编号再加1，所以不应该是top>=m时判断不可行，这样的话在top=m的情况下相当于容量就少了一个了，改为top>m后就正确了。
C.时间复杂度：输入为O(n)。在计算过程中虽然有两元变量i、j在递增，但循环本身只有j++，且注意到操作数最多也不会超过车厢数的两倍，所以时间复杂度为O(n)。
空间复杂度：本程序没有动态规划、递归等的应用，在一开始就申请好了所有的空间以应付n<100000的情况，因此空间复杂度是O(1).
近期下载者：
相关文件：
收藏者：