1046 Shortest Distance （20 分）
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 D?1 D2 ? DN?? , 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 (≤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
分析
若采取常規(guī)方法，測(cè)試點(diǎn)2(starting from 0)會(huì)超時(shí),此處采用<font color="hotpink">空間換時(shí)間降低時(shí)間復(fù)雜度 </font>，具體做法是：在輸入的同時(shí)計(jì)算每個(gè)點(diǎn)到第一個(gè)點(diǎn)的距離雏节，并將它存放在數(shù)組dis中些椒。兩點(diǎn)的距離要么環(huán)的劣弧稍浆，要么是環(huán)的優(yōu)弧脆侮，這里先固定一下即求由a到b的距離（a<b）,另一端距離用總round trip distance(圓環(huán)總長(zhǎng)度)減去這里求的距離藏畅，比較兩者取最小值瓮增，特別地，總距離程序中用虛擬的第n+1點(diǎn)表示虱饿，因?yàn)樗降谝粋€(gè)點(diǎn)的距離恰好等于圓環(huán)長(zhǎng)度拥诡。
圓環(huán)總長(zhǎng)度小于107，那么距離值可以定義為int.
#include<iostream>
using namespace std;
int dis[100010];
int main(){
int n,m;
scanf("%d",&n);
for(int i=1;i<=n;i++) {
int tmpdis;
scanf("%d",&tmpdis);
if(i==1) dis[i+1]=tmpdis;
else dis[i+1]=dis[i]+tmpdis;
}
scanf("%d",&m);
for(int i=0;i<m;i++){
int a,b;
cin>>a>>b;
if(a>b) swap(a,b);
int tmpsum=dis[b]-dis[a];
cout<<min(tmpsum,dis[n+1]-tmpsum)<<endl;
}
return 0;
}
