题目描述
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, 10
5]), followed by N integer distances D
1 D
2 ... D
N, where D
i is the distance between the i-th and the (i+1)-st exits, and D
N 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 (<=10
4), 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 10
7.
输出描述:
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个数则是第i个和第i+ 1个数之间的距离。给你两个结点，然后求这两个结点之间的距离，最后一个结点和第一个结点是相连的。
解析那么这样求最短距离，那么也就是判断两个结点直接的顺时针的距离和逆时针之间的距离那个更小，这样一来就很容易理解了我们就在每次输入一个结点的距离的时候求出该结点和第一个结点的距离，那么之后求这两个结点之间的顺时针的距离也就是这两个结点到第一个结点的距离相减。然后逆时针的距离也就是总的距离减去顺时针的距离，这样一来就很好理解了。
实现：
#include<stdio.h>
#include<algorithm>
using namespace std;
const int MAXN = 100005;
int dis[MAXN], A[MAXN];
int main(){
int n, sum = 0, query, left, right;
scanf("%d", &n);
for(int i = 1; i <= n; i ++){
scanf("%d", &A[i]);//A[i]代表的是第i个结点到第i+1个结点之间的距离，也就是每次需要输入的距离
sum += A[i];
dis[i] = sum;//dis[i]则是第一个结点到第i+1个结点之间的距离，所以第5个结点到第一个结点的距离也就是dis[4]
}
scanf("%d", &query);
for(int i = 0; i < query; i ++){
scanf("%d%d", &left, &right);
if(left > right){
swap(left , right);
}
int temp = dis[right - 1] - dis[left - 1];
printf("%d\n", min(temp, sum - temp));
}
return 0;
}
