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 Ninteger 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
分析： 题目意思是给了一个环，已经环的每条边（公路）的长度，现给出起点和终点，求出起点和终点之间的最短路径长度，即求顺时针和逆时针行驶的距离最小值。
先求顺时针的距离，而逆时针距离=sum-顺时针距离；
另外暴力求解测试点3会超时，因为每次遍历数组，最大情况10^5个顶点，若有10^4个查询，则一共10^9，对于100ms的时限不能承受。
可以在输入距离时用dis数组记录从1顺时针出发到各顶点的距离。
/**
* Copyright(c)
* All rights reserved.
* Author : Mered1th
* Date : 2019-02-23-19.12.21
* Description : A1046
*/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<string>
#include<unordered_set>
#include<map>
#include<vector>
#include<set>
using namespace std;
;
int a[maxn],dis[maxn];
int main(){
#ifdef ONLINE_JUDGE
#else
freopen("1.txt", "r", stdin);
#endif
;
scanf("%d",&n);
;i<=n;i++){
scanf("%d",&a[i]);
sum+=a[i];
dis[i]=sum;
}
scanf("%d",&m);
;i<m;i++){
,ans2=;
scanf("%d%d",&st,&ed);
if(st>ed) swap(st,ed);
ans1=dis[ed-]-dis[st-];
ans2=sum-ans1;
printf("%d\n",min(ans1,ans2));
}
;
}