PAT A1046 Shortest Distance (20)

- 日理万妓 2021-09-13 22:18 266阅读 0赞

**题目地址：**[https://www.patest.cn/contests/pat-a-practise/1046][https_www.patest.cn_contests_pat-a-practise_1046]

**题目描述：**

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.

**输入格式（Input Specification）:**

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.

**输出格式（Output Specification）:**

For each test case, print your results in M lines, each contains the shortest distance between the corresponding given pair of exits.

**输入样例（Sample Input）:**

5 1 2 4 14 9  
3  
1 3  
2 5  
4 1

**输出样例（Sample Output）:**

3  
10  
7

--------------------

**题意：**

有Ｎ个结点围城一个圈，相邻两个点之间的距离已知，且每次只能移动到相邻点。然后给出Ｍ个询问，每个询问给出两个数字Ａ和Ｂ即结点编号（１＜＝Ａ，Ｂ＜＝Ｎ），求从Ａ号结点到Ｂ号结点的最短距离。

**样例解释：**

如图所示，共有５个结点，分别标号为１、２、３、４，相邻两点的距离在图上给出。总共三个询问：  
１３：从１号点到３号点的最短距离为３，路径为１－＞２－＞３；  
２５：从２号点到５号点的最短距离为１０，路径为２－＞１－＞５；  
４１：从４号点到１号点的最短距离为７，路径为４－＞３－＞２－＞１。

--------------------

**解题思路：**

步骤 1：以dis\[ i \]表示 1 号结点按顺时针方向到达”i 号结点顺时针方向的下一个结点“的距离（1 <= i <= N），sum 表示一圈的总距离。于是对每个查询 left ->right，其结果就是 dis( left , right ) 与 sum - dis（left , right）中的较小值。  
步骤 2：dis 数组和 sum 在读入时就可以进行累加得到。这样对每个查询 left -> right，dis（left，right）其实就是 dis\[ right - 1\] - dis\[left - 1\]。这样可以做到查询复杂度为O（1）。

> **注意：**
> 
>  *  查询的两个点的编号可能会有 left > right 的情况。这样情况下，需要交换 left 和 right
>  *  此题若没有经过预处理 dis 数组和 sum 的做法会很容易超时
>  *  之所以不把 dis\[ i \] 设置为 1 号结点按顺时针方向到达 i 号结点的距离，是因为 N 号结点到达 1 号结点的距离无法被这个数组所保存

--------------------

**C++完整代码如下：**

#include<cstdio>
    #include<algorithm>
    using namespace std;
    
    const int MAXN = 100005;
    int dis[MAXN], A[MAXN];    // dis数组含义已说明，A[I] 存放 i 号与 i+1 号顶点的距离
    int main(){
      int sum = 0, query, n, left, right;
      scanf("%d", &n);
      for(int i = 1; i <= n; i++){
        scanf("%d", &A[i]);
        sum += A[i];    //累加 sum
        dis[i] = sum;     //预处理 dis 数组 
      }
      scanf("%d", &query);
      for(int i = 0; i < query; i++){      //query 个查询
        scanf("%d%d", &left, &right);    // left -> right
        if(left > right) swap(left, right);  //left -> right 时交换 
        int temp = dis[right - 1] - dis[left - 1];
        printf("%d\n", min(temp, sum - temp));
      } 
      return 0;
    }

[https_www.patest.cn_contests_pat-a-practise_1046]: https://www.patest.cn/contests/pat-a-practise/1046