1046 Shortest Distance （20 分）(贪心算法)

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,10⁵]), 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 (≤10⁴), 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⁷ .

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

分析

若采取常规方法，测试点2(starting from 0)会超时,此处采用<font color="hotpink">空间换时间降低时间复杂度 </font>，具体做法是：在输入的同时计算每个点到第一个点的距离，并将它存放在数组dis中。两点的距离要么环的劣弧，要么是环的优弧，这里先固定一下即求由a到b的距离（a<b）,另一端距离用总round trip distance(圆环总长度)减去这里求的距离，比较两者取最小值，特别地，总距离程序中用虚拟的第n+1点表示，因为它到第一个点的距离恰好等于圆环长度。
圆环总长度小于10⁷，那么距离值可以定义为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;
}