C++ zoj1259 Rails
|
题目：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1259 一、题目大意： ? ? ? ?A中列车的原始列车序列为：1 2 3 … N，B中存储列车的目标序列，问B中给出的列车目标序列是否可以将A中的原始序列通过中转站station实现。A中的数进station了，就不可以返回到A中。 二、输入输出 输入： 输入由行块组成。 除了最后一个之外的每个块（其实就是每一行）都是描述了一个列车的可能重组要求（就是目标序列）。 在块的第一行中，存储着如上述中的整数N。在接下来的每一行中是由1，2， 3 … N 组成的序列（目标序列）。块的最后一行仅包含0。（该次结束） 最后一个块只包含一行，就是0。（表示整个程序结束） 5? -> 第一组测试数据: N=5 1 2 3 4 5?? -> 这个目标序列可以实现，所以输出"Yes" 5 4 1 2 3 ->? 这个目标序列不可以实现，所以输出"No" 0? -> 第一组测试数据结束 6 -> 表示第二组测试数据块： N=6 6 5 4 3 2 1 -> 这个目标序列可以实现，所以输出"Yes" 0 -> 第二组测试数据结束 0? -> 表示测试完毕，整个程序结束 输出： ?????? 目标序列是否可以实现的结果 注意：输出每一个块测试数据的结果完之后要空一行（N=5），接着输出另一个块(N=6)的的结果。 三、实现思路：用栈 ? ? ?重点是抓住目标序列 ???? （1）判断B中（目标序列）当前的数target[i]的数是否等于A中的数（j）? ????????????? 如果是，则B和A都要往后移一个数，将i和j都加1； ????????????? 如果不是，说明此时B中的数和A中的数不等； ????? （2）如果此时B中的数（target[i]）和A中的数[j]不等： ???????????????????? 是否可以在station中找到B中要的数（栈顶的数和target[i]是否相等）？ ??????????????????????????? 如果是，就把栈顶的数pop掉，同时B中的数往后移一个数(i++) ??????????????????????????? 如果不是，那就要把A中数压入到栈中，再去判断B中此时的数和A中的数是否相等，如果还不相等， ??????????????????????????? 就继续压入到栈中，直到A中没有数了。 四、实现程序 #include #include using namespace std; const int MAXN = 1000; int main() { int i,j,n,target[MAXN]; // arr数组存储目标序列(B中的数据) stack while (cin >> n && n) // 如果n等于0，程序结束 { while (cin >> target[0] && target[0]) //如果target[0]等于0表示当前块的测试结束 { // ?输入目标序列 for (i = 1; i < n; i++) cin >> target[i]; j = 1; // 存储A中的原始数列1,2... N，因为每次自增1，所以用j就行了，不用数组 i = 0; while (i < n) { if (j == target[i]) // 如果目标序列当前的数和j相等（即B中此时的数和A中的数相等） { // 那么A和B都往后移一个数 j++; i++; } else // B中的数和A中的数此时不等 { // 判断station中上面的数（最后进去的）是否等于目标序列 if (!st.empty() && target[i] == st.top()) { // 如果相等，就把栈中（station）的数pop掉 st.pop(); i++; // 目标序列往后移一个数 } else // 如果A和station中的数此时都不等于B中的数，那就把A中的数压入到station（栈）中 { if (j <= n) { // 判断A中的数是否全部已压入到station中 st.push(j); j++; } else break; } } } if (i == n) cout << "Yes" << endl; else cout << "No" << endl; while (!st.empty()) st.pop(); // 释放空间 } cout << endl; } return 0; } 运行结果： （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |