本文共 2393 字，大约阅读时间需要 7 分钟。

Codeup小白掉坑经验总结之 Shortest Distance id=6116

• 题目如下
  6116: Shortest Distance (20)
  时间限制: 1 Sec 内存限制: 32 MB
  献花: 213 解决: 97

题目描述

The task is really simple: given N exits on a highway which forms a simple cycle, you are supposed to tell the shortest distance between any pair of exits. 输入 Each input file contains one test case. For each case, the first line contains an integer N (in [3, 105]), followed by N integer distances D1 D2 … DN, where Di is the distance between the i-th and the (i+1)-st exits, and DN is between the N-th and the 1st exits. All the numbers in a line are separated by a space. The second line gives a positive integer M (<=104), with M lines follow, each contains a pair of exit numbers, provided that the exits are numbered from 1 to N. It is guaranteed that the total round trip distance is no more than 107. 输出 For each test case, print your results in M lines, each contains the shortest distance between the corresponding given pair of exits.

样例输入

5 1 2 4 14 9 3 1 3 2 5 4 1 样例输出 3 10 7

题目意思其实很简单，就是有n个顶点构成一个简单的环，给定n个顶点之间的n条边的距离，然后任给两个顶点，让你输出这两个顶点之间的最短距离

于是乎我写出了如下代码：

#include 
   
    int circle[100000];int main(){       int n,m;    scanf("%d",&n);     int b,e,low,high,dis1,dis2;    for(int i=1;i<=n;i++)    {        scanf("%d",&circle[i]);    }    scanf("%d",&m);    for(int j=0;j
    
     e?b:e);                  for(int i=low;i
    
   

然后自信满满的献了个花，结果被judger鄙视了。。。

本人百般思考，无奈智商欠费，于是只能求助度娘，才发现这题的坑。。都是设计好的，就等着你往下跳(／‵口′)／~╧╧

首先时间限制是1sec，而一般OJ一秒的运算次数为1e7~1e8，这题n最大可以是1e5,而给出一对边的数目m可以是1e4,那么两层循环一嵌套，1e9，正好大于1e8，看，完美的超时了！就是这么巧妙，最后的那个1e7只是告诉你这个总距离用int型表示就可以了，因为int型可以表示绝对值在1e9范围以内的整数。

在百度了各位大神的总结后，我把我的代码修改如下：

#include 
   
    int main(){    int circle[100000],distance[100000];    distance[1]=0;    int n,m,sum=0;    scanf("%d",&n);     int b,e,low,high,dis1,dis2;    for(int i=1;i<=n;i++)    {        scanf("%d",&circle[i]);        sum+=circle[i];        distance[i+1]=distance[i]+circle[i];    }    scanf("%d",&m);    for(int j=0;j
    
     e?b:e);        dis1=distance[high]-distance[low];        dis2=sum-dis1;        if(dis1
    
   

修改后的代码，算法思想和前者就不同了。

首先，在输入每个边的时候，就计算两个量，一个是这个环的总距离，这个用一个sum累加就可以实现，另一个，是第一个顶点距离各个顶点的距离，用一维数组实现，每个顶点的值等于输入的距离加上上一个顶点的值，初始将1这个顶点的值置为0，因为1到1本身就是0嘛。

然后，根据输入的两个顶点，将它们和顶点1之间的距离相减，就得到了其中一个距离，另一个距离通过环的总距离减去这个距离就能得到了，然后比较两个的大小，输出最小的，然后就完成啦ヽ(￣▽￣)ﾉ

这种操作，避免了两重循环，通过简单的变量累加以及四则运算就可以得到最终解，充分说明了一个问题，写代码，要会写，但是，关键还是在于思想，思想错了，再怎么优化代码，也无济于事。嗯….学到了很多(⊙…⊙)。

转载地址：https://meteorrain.blog.csdn.net/article/details/78980478 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！