问题 E: Shortest Distance (20)

第一次的想法码的代码如下（超时）：

1 #include 
     
       2 #include
      
        3 #include
       
         4 #define maxn 100001 5 /* run this program using the console pauser or add your own getch, system("pause") or input loop */ 6 using namespace std;  7 int n; 8 typedef struct Dnode{ 9     int s;10     int e;11     int d;12 }Dnode;13 14 Dnode Dset[maxn];15 int p1,p2;16 void solve(){17     int sum1=0;18     int min;19     int s=p1;20     int e=p2;21     while(s!=e){22         sum1+=Dset[s].d;23         s=Dset[s].e;24     }25     min=sum1;26     sum1=0;27     28     while(s!=p1){29         sum1+=Dset[s].d;30         s=Dset[s].e;31     }32     if(min
        
         >n){45         t=1;46         for(i=1;i<=n;i++){47             cin>>d;48             j=i+1;49             if(j>n) j%=n;50             Dset[t].s=i;51             Dset[t].e=j;52             Dset[t].d=d;53             t++;54         }55         56         cin>>test;57         while(test--){58             cin>>p1>>p2;59             solve();60         }61         62     }63     return 0;64 }
        
       
      
     

上面的代码时间超时

 

第二次优化一下，还超时：

代码如下：

1 #include 
     
       2 #include
      
        3 #include
       
         4 #define maxn 100001 5 /* run this program using the console pauser or add your own getch, system("pause") or input loop */ 6 using namespace std;  7 int n; 8 typedef struct Dnode{ 9     int s;10     int e;11     int d;12 }Dnode;13 14 Dnode Dset[maxn];15 int p1,p2;16 int total_d;17 void solve(){18     int sum1=0;19     int min;20     int s=p1;21     int e=p2;22     while(s!=e){23         sum1+=Dset[s].d;24         s=Dset[s].e;25     }26     min=sum1;27     sum1=total_d-min;28     if(min
        
         >n){41         t=1;42         total_d=0;43         for(i=1;i<=n;i++){44             cin>>d;45             total_d+=d;46             j=i+1;47             if(j>n) j%=n;48             Dset[t].s=i;49             Dset[t].e=j;50             Dset[t].d=d;51             t++;52         }53         54         cin>>test;55         while(test--){56             cin>>p1>>p2;57             solve();58         }59         60     }61     return 0;62 }
        
       
      
     

暂时还没想到哪可以优化，不过我估摸着，得预先把每个点的最小值弄出来，因为M最大为10^4,而N最大为10^6 M*N=10^10 严重超时！

如果我能预先把它算出来的话最大的复杂度为O(10^4)

 

---

13:37:20   2019-03-30

第三次写：

值得注意的是对于二维数组长度不能超过10000,否则会报错的！而且提交上去，会编译错误！  如果你改小数组大小，回报出运行错误！

后来想，我保存一下每一组的最大值不就行了？结果发现不行，因为二维数组太大了！

由于数组大小太小而运行出错的代码如下：

1 #include 
     
       2 #include
      
        3 #include
       
         4 #define maxn 10001 5 /* run this program using the console pauser or add your own getch, system("pause") or input loop */ 6 using namespace std;  7 int n; 8 int min_d[maxn][maxn];//存储i->j的最短距离 9  10 typedef struct Dnode{11     int s;12     int e;13     int d;14 }Dnode;15 16 Dnode Dset[maxn];17 int p1,p2;18 int total_d;19 void solve(){20     int sum1=0;21     int min;22     int s=p1;23     int e=p2;24     while(s!=e){25         sum1+=Dset[s].d;26         s=Dset[s].e;27     }28     min=sum1;29     sum1=total_d-min;30     if(min>sum1) 31         min=sum1;32     min_d[p1][p2]=min_d[p2][p1]=min;33     cout<
        
         <
         
          >n){44         t=1;45         total_d=0;46         memset(min_d,0,sizeof(min_d));47         for(i=1;i<=n;i++){48             cin>>d;49             total_d+=d;50             j=i+1;51             if(j>n) j%=n;52             Dset[t].s=i;53             Dset[t].e=j;54             Dset[t].d=d;55             t++;56         }57         58         cin>>test;59         while(test--){60             cin>>p1>>p2;61             if(min_d[p1][p2]!=0)62                 cout<
          
           <
          
         
        
       
      
     

 

于是我又想，二维数组不行，那一位数组保存不就行了？

想到这个我就想到了一个东西：

思考一下：如果我知道d12 、d13 、d14  、d15 的距离，是不是能求出任意两点的距离呢？肯定能求出

dij=d1j-d1i  （*）

一旦你想到了(*)式，你就离正确的答案不远了！

于是我就设了一个数组 d_total[maxn] ，其中

d_total[2] 表示从1-2的距离

d_total[3] 表示 1-3的距离

  .....

d_total[5] 表示1-5的距离

.....

还能优化的是：假如你求出的dij大于半个圆的长度，那最短的就是 : 这个圆的周长-dij

 

如图所示：

看完这个图片，应该是很清楚了，话不多说，代码如下

AC了的代码：

1 #include 
     
       2 #include
      
        3 #include
       
         4 #define maxn 100001 5 /* run this program using the console pauser or add your own getch, system("pause") or input loop */ 6 using namespace std;  7  8 int d_total[maxn]; 9 /*d_total[2] 表示从1-2的距离 10   d_total[3] 表示 1-3的距离11   .....12   d_total[5] 表示1-5的距离 13  */ 14 15 16 int p1,p2;17 int n;//它在main函数里面的话，n会为0 18 void solve(){19     int d;20     d=d_total[p2]-d_total[p1]; //因为我默认是1为起点的 21     if(d
        
         >n){33         t=2;34         35     36         for(i=1;i<=n;i++){37             cin>>d;38             d_total[t]+=d_total[t-1]+d;39             t++; 40             41         }42         43         int temp;44         cin>>test;45         while(test--){46             cin>>p1>>p2;47             if(p1>p2){
   //因为在solve()函数中我默认p2是大于p1的，而题目给的不一定，所以要交换 48                 temp=p1;49                 p1=p2;50                 p2=temp;51             }52             53             solve();54         }55         56     }57     return 0;58 }
        
       
      
     

 

---

我想多说一句：通过这道题我感受到了优化的魅力和算法的魅力.所以，当我们对一道题可能弄不出来的时候，不要轻易去看答案，而是要自己独立思考！总会做出来的！代码是朋友...