PTA甲级——1046

1046 Shortest Distance

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 D**i 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:

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

Sample Output:

1
2
3
3
10
7

思路

​ 大致题意：输入一个n,后面的第i个数表示i～i+1之间的距离，第n个数表示n～1之间的距离，然后再输入一个k,后面的k组数据，每组数据有两个数l,r,我们需要求两个数之间的最短距离。

​ 思路：简单的前缀和应用。

代码

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
#include <iostream>
#include <cmath>

using namespace std;
const int  N = 1e5 + 10, M = 2 * N;
int n;
int a[N];
int cnt[N];

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        cnt[i + 1] = cnt[i] + a[i];
        // cout << i + 1 << " " << cnt[i + 1] << '\n';
    }
    int k;
    cin >> k;
    // 0 1 3 7 21 30
    for (int i = 1; i <= k; i++){
        int l, r;
        cin >> l >> r;
        cout << min(abs(cnt[r] - cnt[l]), cnt[n + 1] - abs(cnt[r] - cnt[l])) << '\n';
    }

    return 0;
}