1046 Shortest Distance

发表于

地铁环状线两点之间的距离为t，最小值为t或则是周长-t。（t为按起点到终点由小到大，大减小而来）

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    int dis[n + 2] = {0};
    int sum = 0, left, right, cnt;
    for (int i = 1; i <= n; i++) {
        int t;
        scanf("%d", &t);
        sum += t;
        dis[i + 1] = sum;
    } // dis[i]表示i点的绝对距离，dis[1] = 0，dis[n+1]意思是走一圈的距离
    scanf("%d", &cnt);
    for (int i = 0; i < cnt; i++) {
        scanf("%d %d", &left, &right);
        if (left > right) { swap(left, right); }
        int t = dis[right] - dis[left];
        printf("%d\n", min(t, dis[n + 1] - t));
    }

    return 0;
}

5 1 2 4 14 9
3
1 3
2 5
4 1

3
10
7

// 也可以用
    for(int i = 1; i <= n; i++) {
        int temp;
        scanf("%d", &temp);
        sum += temp;
        dis[i] = sum;
    }
// 表示的是从第一个点到i下一个点的距离
// 所以dis[n]是从第一点到n点再毁1点的距离（即总长）
// 两点距离得用int temp = dis[right - 1] - dis[left - 1];来表示。
// 比如2 6，temp = dis[2-1]-dis[6-1]，
// 因为dis[1]表示从1点到2点的距离，dis[5]表示从1点到6点的距离