入门经典紫书第五章木块问题（UVa 101）答案超时但与书上答案几乎相同

Question

自己的答案

 #include<cstdio>
#include<string>
#include<vector>
#include<iostream>
using namespace std;

const int maxn = 30;
vector<int> Dui[maxn];
int n;

void print(){
     for(int i = 0 ; i<n ; i++){
         printf("%d:",i);
         for(int j = 0;j<Dui[i].size();j++){
            printf(" %d",Dui[i][j]);
         }
         printf("\n");
     }
}

void Find_block(int &p , int &h , int x){
    for(p = 0 ; p<n ; p++){     //要找到位置，那么就不能使用局部变量，要让位置变化
       for(h = 0 ; h<Dui[p].size(); h++){   //因为在vector中列数是不确定的，可以随时增减
          if(Dui[p][h] == x) return;  //直接结束调用，因为位置都为全局变量，返回的位置就是p(p1,p2),h(h1,h2)
       }
    }
}

void Move_back(int p, int h){
     int x;
     for(int i = h+1 ; i<Dui[p].size() ; i++){
         x = Dui[p][i];
         Dui[p].push_back(x);
     }
     Dui[p].resize(h+1);
}

void Move_change(int pa,int pb,int ha){
      for(int i = ha; i<Dui[pa].size() ; i++){
           Dui[pb].push_back(Dui[pa][i]);
      }
      Dui[pa].resize(ha);
}

int main(){
   int a,b;
   string s1,s2;
   cin>>n;
   for(int i = 0;i<n;i++){
        Dui[i].push_back(i);
   }
   while(cin>>s1>>a>>s2>>b){
       int pa,pb,ha,hb;
       Find_block(pa,ha,a); //直接将位置返回给pa，ha；
       Find_block(pb,hb,b);
       if(pa==pb) continue;
       if(s1=="move") Move_back(pa,ha);
       if(s2=="onto") Move_back(pb,hb);
       Move_change(pa,pb,ha);
   }
   print();
   return 0;
}

书上的答案

 #include<cstdio>
#include<string>
#include<vector>
#include<iostream>
using namespace std;

const int maxn = 30;
int n;
vector<int>pile[maxn];

void find_block(int a, int &p, int &h){
    for(p=0 ; p<n ; p++)
      for(h=0; h<pile[p].size(); h++)
        if(pile[p][h]==a) return;
}

void clear_above(int p , int h){
   for(int i = h+1; i<pile[p].size(); i++){
       int b = pile[p][i];
       pile[b].push_back(b);
   }
   pile[p].resize(h+1);
}

void pile_onto(int p , int h, int p2){
   for(int i = h; i<pile[p].size(); i++)
      pile[p2].push_back(pile[p][i]);
   pile[p].resize(h);
}

void print(){
   for(int i = 0; i < n ; i++){
      printf("%d:",i);
      for(int j = 0; j < pile[i].size(); j++) printf(" %d",pile[i][j]);
      printf("\n");
   }
}

int main(){
   int a,b;
   cin >> n;
   string s1,s2;
   for(int i = 0; i<n; i++) pile[i].push_back(i);
   while(cin >> s1 >> a >> s2 >> b){
      int pa, pb, ha, hb;
      find_block(a, pa, ha);
      find_block(b, pb, hb);
      if(pa==pb) continue;
      if(s2 == "onto") clear_above(pb, hb);
      if(s1 == "move") clear_above(pa, ha);
      pile_onto(pa, ha, pb);
   }
   print();
   return 0;
}

已经找了一个小时了精疲力竭，实在不明白哪里超时，望各位大神相助，不胜感激

Answer 1

哦，上面的分析有点问题，是对应书上的代码，但是它是把p的数据移动到b，不是移动到p本身。只找了这个点，其他你自己再看看。

void clear_above(int p , int h){
   for(int i = h+1; i<pile[p].size(); i++){
       int b = pile[p][i];
       pile[b].push_back(b);
   }
   pile[p].resize(h+1);
}