http://codeup.hustoj.com/problem.php?cid=100000575&pid=4

題目描述

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

/*《算法筆記》上解釋的非常詳細(xì)，下面是我的理解?

輸入解釋：第一行的5就是有5個(gè)節(jié)點(diǎn)，后面的5個(gè)數(shù)是相鄰節(jié)點(diǎn)1-2，2-3......5-1的距離

第二行的3指的是我們要求三組節(jié)點(diǎn)之間的最短路徑

第三行就是求第1個(gè)節(jié)點(diǎn)到第3個(gè)節(jié)點(diǎn)的距離

......以此類推?

題目的大概要求就是有一個(gè)圓，圓上有n個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)間都給出了距離，

然后去求某個(gè)節(jié)點(diǎn)到某個(gè)節(jié)點(diǎn)之間的最短距離，而且每次只能移動(dòng)到相鄰節(jié)點(diǎn)。

那么怎么做呢？

首先，它限制了只能移動(dòng)到相鄰節(jié)點(diǎn)，也就是說一個(gè)節(jié)點(diǎn)只能順時(shí)針或逆時(shí)針移動(dòng)

（不會(huì)有人抬杠，這個(gè)節(jié)點(diǎn)順時(shí)針走一次，再逆時(shí)針走一次吧）

所以說，問題就變得簡(jiǎn)單了，我們只要比較它是逆時(shí)針和逆時(shí)針哪個(gè)是最短距離就好了

首先我們需要有一個(gè)記錄總路程的sum，和一個(gè)記錄每一次輸入兩點(diǎn)之間距離的數(shù)組A[i]

在輸入每個(gè)距離的時(shí)候，把它加到sum上就很容易得出總路程。

我們還要有個(gè)記錄某個(gè)點(diǎn)到某個(gè)點(diǎn)（順/逆時(shí)針）的距離temp，我一開始想用循環(huán)，把某個(gè)節(jié)點(diǎn)

到某個(gè)節(jié)點(diǎn)的距離加起來，參考了答案后，可以看出它用了一個(gè)更容易的方法

就是我們?cè)谇髎um的時(shí)候可以得到第1個(gè)節(jié)點(diǎn)到其他i個(gè)節(jié)點(diǎn)的距離dis[]，比如我們想要得到第2個(gè)節(jié)點(diǎn)

到第5個(gè)節(jié)點(diǎn)的距離，我們就可以用1到5的距離減去1到2的距離，如圖2，再用min函數(shù)（用c++的原因）

求出最小值。*/