首页 > 代码库 > 火车车厢重排问题
火车车厢重排问题
2014-11-04
主要数据结构：栈
题目：一列火车要将n节车厢分别送往n个车站按1~n的次序编号，火车按照n,n-1,…1的编号次序经过车站。假设车厢的编号就是其目的地车站的编号。
要求：给定一个任意的车厢排列次序。重新排列车厢，使其按照从1到n的次序排列。规定重排时，只能从入轨到缓冲铁轨，或者从缓冲铁轨到出轨。
总的思路：
首先：将所需要重排的车厢编号从左到右依次输入数组carrage中；
然后：对carrage中的元素进行从左往右逐个遍历，如果符合下一个输出，则直接将其输出，并且遍历所有的缓冲轨道，查找是否有符合下一个输出的车厢，有的话便将其输出，否则将其压入缓冲轨道
未经优化的代码：
1 #include <iostream> 2 #include <stack> 3 using namespace std; 4 5 stack<int> stack_final; 6 7 8 void Output(int& minH, int& minS, stack<int> H[], int k, int n) { 9 // put the car from the strack to the output line, and change the minH and minS 10 int index; // the index of the car 11 //delete the minist car number from the minS 12 stack_final.push(H[minS].top()); 13 H[minS].pop(); 14 cout << "Move car " << minH << "from holding track " << minS << " to output line" << endl; 15 //serch all the track‘s top, find the new minH and minS 16 minH = n+2; 17 for (int i= 0; i < k; i++) { 18 if (!H[i].empty() && (index = H[i].top()) < minH) { 19 minH = index; 20 minS = i; 21 } 22 } 23 } 24 25 bool Input(int c, int& minH, int& minS, stack<int> H[], int k, int n) { 26 // put the new car c into the track 27 // if there is no available track, then return false, else return true 28 // find the best track for the car c 29 // initial 30 int BestTrack = 0; //the best track now 31 int BestTop = n+1; //the best track‘s top car 32 int index; //the index for the car 33 // search the k track 34 for (int i= 0; i < k; i++) { 35 if (!H[i].empty()) { 36 index = H[i].top(); 37 if (c < index && index < BestTop) { 38 //the top car‘s number is the smallest 39 BestTop = index; 40 BestTrack = i; 41 } 42 } else { // the track is empty 43 if (!BestTrack) { 44 BestTrack = i; 45 } 46 } 47 } 48 if (!BestTrack) { 49 return false; //there is available track to use 50 } 51 H[BestTrack].push(c); 52 cout << "Move car " << c << "from input to holding track " << BestTrack << endl; 53 //if it is essencial, then change the minH and minS 54 if (c < minH) { 55 minH = c; 56 minS = BestTrack; 57 } 58 return true; 59 } 60 61 bool Railroad(int input[], int n, int k) { 62 //k 63 // if it resort succed, then return true, else return false 64 // create the stack according to the k 65 stack<int> *H; 66 H = new stack<int> [k]; 67 int NowOut = 1; // the next number of car to putout 68 int minH = n+1; //the minist number car in the k 69 int minS; //the minist number‘s strack 70 // resort the car 71 for (int i = n-1; i >= 0; i--) { 72 int number = input[i]; 73 if (number == NowOut) { 74 cout << "Move car " << number << " from the input line to the output line\n"; 75 stack_final.push(number); 76 NowOut++; 77 while (minH == NowOut) { 78 Output (minH, minS, H, k, n); 79 NowOut++; 80 } 81 } else { 82 int end = 0; 83 for (int j = i; j > 0; j--) { 84 if (input[j-1] < input[j]) { 85 end = j; 86 break; 87 } 88 } 89 for (int j = end; j <= i; j++) { 90 if (!Input (input[j], minH, minS, H, k, n)) { 91 return false; 92 } 93 } 94 if (end) { 95 i = end; 96 } 97 } 98 } 99 return true;100 }101 102 int main() {103 int n, *input;104 cin >> n;105 input = new int[n];106 for (int i = 0; i < n; i++) {107 cin >> input[i];108 }109 if (Railroad(input, n, n-1)) {110 cout << "resort succed!\n";111 while (!stack_final.empty()) {112 cout << stack_final.top() << " ";113 stack_final.pop();114 }115 } else {116 cout << "failed\n";117 }118 }
经过优化之后的代码：
增加的条件：车厢可以从排在后面的缓冲轨道移到前面的缓冲轨道。
优化算法：
1：压入缓冲轨道：
首先：以要入栈的车厢为始端，遍历carrage，找到一段连续递增的序列，如果没有连续递增序列，则只将该车厢压入缓冲轨道，否则，将该段递增序列压入到缓冲轨道
只有一个车厢等待压入缓冲轨道：遍历所有的缓冲轨道，查找栈顶元素编号大于并且最接近该车厢编号，若有符合条件的轨道，则直接压入，否则创建一个新的空轨道用作该车厢的缓冲轨道。并且对所有缓冲轨道的车厢进行调整，以最接近且上面小于下面为原则。
有一段连续递增序列车厢等待压入缓冲轨道：采用一个临时栈，一个目标栈，利用“倒水”的方法将该段递增序列压入缓冲轨道，与此同时，为每一个寻找最优轨道。
2：每一次将车厢送入缓冲轨道之后，都对缓冲轨道进行一遍优化。
1 #include<iostream> 2 #include<stack> 3 using std::stack; 4 using std::cin; 5 using std::cout; 6 7 const int MAX = 100; //缓冲栈的最大数目 8 const int INF = 0x7fffffff; 9 10 class trainDispatch{ 11 public: 12 trainDispatch(); //读入待排序的车厢编号数目和车厢编号，并储存在carrage[]中 13 void solution(); //对待排序的车厢进行排序并不断输出 14 private: 15 stack<char> stackArray[MAX]; //缓冲栈 16 int carrageNum; //储存车厢数 17 int usedStackNum; //已经使用过的缓冲轨道数 18 int carrage[MAX]; //原始车厢序列 19 int expectNum; //待输出的车厢编号 20 21 int findIncrementEnd(int start); //找到carrage[start]开始的最大的递增项，返回其索引 22 int findFirstEmpty(int st, int ed); //找到第一个空的缓冲轨道 23 int findNearestBigger(int x, int st, int ed); //遍历st到ed之间的缓冲轨道，寻找大于且最接近x的缓冲轨道编号，若存在，返回该轨道编号，否则，返回-1. 24 void move (int stIndex, int edIndex, int tempStack, int inStack); //以tempStack为临时缓冲栈编号，inStack为目标栈编号，将stIndex到edIndex之间的车厢编号压 入inStack 25 int findLargestTop(int st, int ed); //遍历编号介于st与ed之间的缓冲轨道，寻找栈顶元素最大的轨道编号 26 int findLargestLessThan(int index, int st, int ed); //遍历编号介于st与ed之间的缓冲轨道，寻找栈顶元素最大且小于编号为index轨道的栈顶元素的轨道编号 27 28 void MoveInSingle(int Index); //只将编号为carrage[index]的车厢压入缓冲轨道 29 void MoveInMoreThanOneSimple(int startIndex, int endIndex); //将车厢编号从carrage[startIndex]到carrage[endIndex]的连续递增轨道压入缓冲轨道 30 void MoveInMoreThanOneComplex(int startIndex, int endIndex); //将车厢编号从carrage[startIndex]到carrage[endIndex]分为连续递增段并压入缓冲轨道 31 void MoveOut(int&); //遍历所有的缓冲轨道，若有符合下一个输出的元素，则将其输出 32 void adjust(int st, int ed); //对缓冲轨道进行优化 33 }; 34 35 /* 输入所需要重排的车厢数目和车厢序列/ 36 车厢序列的读取方法为从左往右 */ 37 trainDispatch::trainDispatch() { 38 usedStackNum = 0; cout << "please enter the number of the carrages:\n"; 39 cin >> carrageNum; 40 cout << "please enter the serial number in order\n"; 41 for (int i = 0; i < carrageNum; i++) { 42 cin >> carrage[i]; 43 } 44 } 45 46 void trainDispatch::solution() { 47 int ed; 48 int expectNum = 1; 49 /* 从左往右依次遍历车厢号，若不符合输出，则将车厢号压入缓冲轨道/ 50 否则，将其输出，并遍历各个缓冲轨道，查询是否有符合条件的输出*/ 51 for (int i = 0; i < carrageNum ; i++) { 52 if (carrage[i] != expectNum) { 53 ed = findIncrementEnd(i); //判断该车厢与其后面排列的车厢是否为递增关系，若不是则只将该车厢压入缓冲轨道 54 // 否则将该串递增序列压入缓冲轨道 55 if (ed == i) { //无递增关系 56 MoveInSingle(i); 57 } else { //i 到 ed之间为递增 58 MoveInMoreThanOneComplex(i, ed); //将i-ed之间的元素压入缓冲轨道 59 i = ed; 60 } 61 } else { 62 cout << "the carrage-" << carrage[i] << " move straightly, doesn`t move into any stack\n"; 63 expectNum++; 64 MoveOut(expectNum); //遍历所有的缓冲轨道，查找是否有符合下一个输出 65 } 66 adjust(0, usedStackNum-1); //遍历所有的缓冲轨道，根据轨道的栈顶元素，对轨道进行优化 67 } 68 } 69 70 /*寻找以carrage[start]为始的递增序列，返回最大项的索引ed*/ 71 int trainDispatch::findIncrementEnd(int start) { 72 int ed = start; 73 while (carrage[ed] < carrage[ed+1]) { 74 ed++; 75 } 76 return ed; 77 } 78 79 /*寻找st到ed之间的第一个空栈，返回空栈的索引i*/ 80 int trainDispatch::findFirstEmpty(int st, int ed) { 81 int i = st; 82 for (i = st; i <= ed; i++) { 83 if (stackArray[i].empty()) { 84 break; 85 } 86 } 87 return i; 88 } 89 90 /* 遍历所有的缓冲轨道，寻找与所要入栈的元素x最接近且大于该元素的符合条件的缓冲轨道，返回该轨道的索引munNum*/ 91 int trainDispatch::findNearestBigger(int x, int st, int ed) { 92 int i; 93 int min = INF; 94 int minNum = -1; 95 for (i = st; i <= ed; i++) { 96 if (!stackArray[i].empty() && stackArray[i].top() > x) { 97 if (min > stackArray[i].top()-x) { 98 min = stackArray[i].top()-x; 99 minNum = i;100 }101 }102 }103 return minNum;104 }105 106 /*遍历编号介于st与ed之间的缓冲轨道，寻找栈顶元素最大且小于编号为index轨道的栈顶元素的轨道编号,返回该轨道编号num*/107 int trainDispatch::findLargestLessThan(int index, int st, int ed) {108 int num = -1;109 int largest = 0;110 for (int i = st; i <= ed; i++) {111 if (!stackArray[i].empty() && stackArray[i].top() < stackArray[index].top())112 if (largest < stackArray[i].top()) {113 largest = stackArray[i].top();114 num = i;115 }116 }117 return num;118 }119 120 /*将carrage[stIndex]与carrage[edIndex]之间的元素压入栈；121 tempStack作为临时栈的编号，inStack作为目标栈的编号*/122 /*将递增车厢从stIndex~edIndex-1先压入一个缓冲栈stackArray[tempStack],123 将最大项直接压入目标栈stackArray[inStack]*/124 /*逐个遍历缓冲栈stackArray[tempStack]中的元素，并将其压入最优缓冲轨道125 对于缓冲栈最后一个元素，考虑可能将其压回该缓冲栈的情况*/126 void trainDispatch::move (int stIndex, int edIndex, int tempStack, int inStack) {127 for (int i = stIndex; i < edIndex; i++) {128 stackArray[tempStack].push(carrage[i]);129 cout << "the carrage-" << carrage[i] << " move into the stack-" << tempStack+1 << "\n";130 }131 stackArray[inStack].push(carrage[edIndex]);132 cout << "the carrage-" << carrage[edIndex] << " move into the stack-" << inStack+1 << "\n";133 for (int i = edIndex-1; i > stIndex; i--) {134 int temp = stackArray[tempStack].top();135 stackArray[tempStack].pop();136 int in = findNearestBigger(temp, tempStack+1, usedStackNum-1);137 stackArray[in].push(carrage[i]);138 cout << "the carrage-" << carrage[i] << " move out of stack-" << tempStack+1139 << ", then move in the stack-" << in+1<< "\n";140 }141 142 stackArray[tempStack].pop();143 int in = findNearestBigger(carrage[stIndex], tempStack, usedStackNum-1);144 stackArray[in].push(carrage[stIndex]);145 if (in != tempStack) {146 cout << "the carrage-" << carrage[stIndex] << " move out of stack-" << tempStack+1147 << ", then move in the stack-" << in+1<< "\n";148 }149 }150 151 /*遍历编号st到ed间的缓冲轨道，寻找栈顶车厢编号最大的栈，返回该栈的索引num*/152 int trainDispatch::findLargestTop(int st, int ed) {153 int num = -1;154 int largest = 0;155 for (int i = st; i <= ed; i++) {156 if (! stackArray[i].empty()) {157 if (largest < stackArray[i].top()) {158 largest = stackArray[i].top();159 num = i;160 }161 }162 }163 return num;164 }165 166 /*只将一个车厢压入缓冲轨道*/167 /*在所有的缓冲轨道中找不到比要入栈元素更大的栈；则寻找第一个空栈*/168 /*若原有栈的数目不够，即没有空栈，则再创建一个空栈*/169 void trainDispatch::MoveInSingle(int Index) {170 int emptyIndex;171 int in = findNearestBigger(carrage[Index], 0,usedStackNum-1);172 if (in == -1) { 173 emptyIndex = findFirstEmpty(0, usedStackNum-1);174 if (emptyIndex >= usedStackNum) { 175 usedStackNum++;176 }177 stackArray[emptyIndex].push(carrage[Index]);178 cout << "the carrage-" << carrage[Index] << " move into the stack-" << emptyIndex+1 << "\n";179 } else {180 stackArray[in].push(carrage[Index]);181 cout << "the carrage-" << carrage[Index] << " move into the stack-" << in+1 << "\n";182 }183 }184 185 /*将连续递增的车厢压入缓冲轨道*/186 /*遍历所有缓冲轨道，若有符合条件的非空栈，则将其作为目标栈187 否则，寻找空栈作为目标栈*/188 void trainDispatch::MoveInMoreThanOneSimple(int startIndex, int endIndex) {189 int in = findNearestBigger(carrage[endIndex], 0, usedStackNum-1);190 if (in > 0 && in < usedStackNum) {191 move(startIndex, endIndex, 0, in);192 }193 if (in == -1) {194 int firempty = findFirstEmpty(0, usedStackNum-1);195 if (firempty == usedStackNum) { //所用过的栈中无空栈 196 //用过的栈的数目为0197 if (usedStackNum == 0) {198 usedStackNum+=2; //创建两个新栈，一个作为临时缓冲栈，一个作为目标栈199 move(startIndex,endIndex, 0, 1);200 } else { //用过的栈不为空，且用过的栈的数目大于0 201 usedStackNum++;202 move(startIndex,endIndex, 0, usedStackNum-1);203 }204 } else { //所用过的栈中有空栈205 if (firempty == 0) { //第一个是空栈 206 int secEmpty = findFirstEmpty(firempty+1, usedStackNum-1); //再次寻找另一个空栈207 if (secEmpty == usedStackNum) {208 usedStackNum++;209 }210 move(startIndex,endIndex, firempty, secEmpty);211 } else {212 move(startIndex,endIndex, 0, firempty); //第一个不是空栈，将第一个作为临时缓冲栈213 }214 }215 }216 if (in == 0) {217 in = findNearestBigger(carrage[endIndex], 1, usedStackNum-1);218 if (in >= 1 && in < usedStackNum) {219 move(startIndex, endIndex, 0, in);220 } else {221 int firempty = findFirstEmpty(1, usedStackNum-1);222 if (firempty == usedStackNum) {223 usedStackNum++;224 }225 move(startIndex,endIndex, 0, firempty);226 }227 }228 }229 230 /*将递增序列车厢压入缓冲轨道*/231 /*将该段递增序列不同的连续递增段*/232 /*例如：原缓冲轨道中有编号6的车厢，待压入的递增序列为34578，此时以6位界限，将其分为345和78分别压入缓冲轨道*/233 void trainDispatch::MoveInMoreThanOneComplex(int startIndex, int endIndex) {234 int div;235 int in;236 for (div = endIndex; div >= startIndex; div--) {237 in = findNearestBigger(carrage[div], 0, usedStackNum-1);238 if (in > 0 && in < usedStackNum) {239 if (startIndex == div) {240 MoveInSingle(div);241 } else {242 MoveInMoreThanOneSimple(startIndex, div);243 }244 if (div+1 == endIndex) {245 MoveInSingle(endIndex);246 }247 if (div+1 < endIndex) {248 MoveInMoreThanOneSimple(div+1, endIndex);249 }250 break;251 }252 }253 if (div < startIndex) {254 MoveInMoreThanOneSimple(startIndex, endIndex);255 }256 }257 258 /*遍历所有的缓冲轨道，将符合下一个输出条件的车厢输出至出轨*/259 void trainDispatch::MoveOut(int& expectNum) {260 bool con = true;261 while (con) {262 con = false;263 for (int k = 0; k < usedStackNum; k++) {264 if (!stackArray[k].empty()) {265 if (stackArray[k].top() == expectNum) {266 con = true;267 stackArray[k].pop();268 cout << "the carrage-" << expectNum << " move out of the stack-" << k+1 << "\n";269 expectNum++;270 }271 }272 }273 }274 }275 276 /*遍历编号从st到ed之间的所有缓冲轨道，尽可能对其进行优化*/277 void trainDispatch::adjust(int st, int ed) {278 int largest = findLargestTop(st, ed);279 if (largest == -1) { //若均为空栈，不用调整 280 return;281 }282 while (largest != -1) {283 int leftLargest = findLargestLessThan(largest, st, largest-1);284 while (leftLargest != -1) {285 int temp = stackArray[leftLargest].top();286 stackArray[leftLargest].pop();287 if (stackArray[leftLargest].empty() || stackArray[leftLargest].top() > stackArray[largest].top()) {288 stackArray[largest].push(temp);289 cout << "the carrage-" << temp << " move out of stack-" << leftLargest+1290 << ", then move in the stack-" << largest+1<< "\n";291 largest = findLargestTop(st, ed);292 break;293 } else {294 stackArray[leftLargest].push(temp);295 leftLargest = findLargestLessThan(leftLargest, st, largest-1);296 }297 }298 if (leftLargest == -1) {299 largest = findLargestLessThan(largest, st, ed);300 }301 }302 }303 304 int main() {305 trainDispatch t;306 t.solution();307 return 0;308 }
火车车厢重排问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。