Codeup墓地—问题 E: Shortest Distance (20)

水深无声 2022-02-28 00:06 209阅读 0赞

## 题目描述 ##

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

#include <stdio.h>
    
    int main()
    {
        int sum=0,sum1,sum2,n,m,head,tail,a[100001];
        scanf("%d",&n);
        for(int i=0; i<n; i++)
        {
            scanf("%d",&a[i]);
            sum+=a[i];      //求出环内总距离长sum
        }
        scanf("%d",&m);     //m组求值数据
        for(int i=0; i<m; i++)
        {
            sum1=0;
            scanf("%d %d",&head,&tail);
            if(head>tail)     //进行调整，总是求顺时针的值
            {
                int tmp=head;
                head=tail;
                tail=tmp;
            }
            for(int j=head-1; j<=tail-2; j++)  //顺时针的值sum1
                sum1+=a[j];
            sum2=sum-sum1;   //逆时针的值sum2
            if(sum2<sum1)    //输出顺时针与逆时针的最小值
                printf("%d\n",sum2);
            else
                printf("%d\n",sum1);
        }
        return 0;
    }

运行结果：  
![2019032318520093.PNG][]

[2019032318520093.PNG]: /images/20220228/3ac6f7b53a784f06969acd9205450973.png