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

自己的答案

 #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;
}

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

3个回答

哦,上面的分析有点问题,是对应书上的代码,但是它是把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);
}
m0_37632283
眼里一片海 非常感谢~,是这个错误,已采纳
2 年多之前 回复
m0_37632283
眼里一片海 额...回复代码打不上,我的代码也是把p的数据传到一个值,只不过书上的变量名是b 我的变量名是x
2 年多之前 回复
m0_37632283
眼里一片海 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); }
2 年多之前 回复
m0_37632283
眼里一片海 ...
2 年多之前 回复

你可以用vs的性能分析工具看耗时的函数:https://blog.csdn.net/u011430225/article/details/47973245
目前手上没有环境,没法帮你看。你有看不懂再问。

m0_37632283
眼里一片海 非常感谢大佬,还不太会使用VS操作C++,以后一定多加学习。再次感谢,问题已解决。
2 年多之前 回复

书里是从p移动到p2,if(pa==pb) continue; p和p2不会相等

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);
}

你这个方法有问题,是从p队列不停把p队列数据加到p队列尾,如果循环取size是没有编译器优化的话,会死循环到内存溢出。

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);
}

feelcycle_07
默默悟问 对应书是clear_above方法,clear_above方法里是从p移动到b,不是从p到p
2 年多之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问