PAT 1046. Shortest Distance (20)

Posted on Edited on In

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 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

所有的数字绕成一个环，从一点到另一个点得距离最小的就是顺时针和逆时针绕的中最小的，顺时针和逆时针是满足顺 + 逆 = 所有的距离的和的，这里的dis保存的是从1到i的顺时针路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

int main() {
    int n = 0, sum = 0;
    scanf("%d", &n);
    int *dis = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        int t = 0;
        scanf("%d", &t);
        dis[i] = dis[i - 1] + t;
        sum += t;
    }
    int m = 0;
    scanf("%d", &m);
    for (int i = 0; i < m; i++) {
        int a = 0, b = 0;
        scanf("%d %d", &a, &b);
        if (a > b) swap(a, b);
        int t = dis[b - 1] - dis[a - 1];
        printf("%d\n", min(t, sum - t));
    }
    delete[] dis;
    return 0;
}