A1046 Shortest Distance (20分)

代码长度限制 16 KB
时间限制 200 ms
内存限制 64 MB

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^5^]), followed by N integer distances D~1~ D~2~ ⋯ D~N~, where D~i~ is the distance between the i-th and the (i+1)-st exits, and D~N~ 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^4^), 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^7^.

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

Coding:

#include <iostream>
using namespace std;

const int SIZE = 10000;
int main() {
    int N, M, distance[SIZE] = {0}, start[SIZE] = {0}, end[SIZE] = {0};
    cin >> N;
    for (int i = 0; i < N; i++)
        cin >> distance[i];

    cin >> M;
    for (int i = 0; i < M; i++) {
        cin >> start[i] >> end[i];
        if (start[i] > end[i])
        {
            int swap;
            swap = start[i];
            start[i] = end[i];
            end[i] = swap;
        }
    }

    int t;
    int result[SIZE] = {0}, T[SIZE] = {0};
    for (int i = 0; i < M; i++)
    {
        t = start[i] - 1;
        while (t != end[i] - 1) {
            result[i] += distance[t];
            t++;
        }
    }

    for (int i = 0; i < M; i++)
    {
        t = end[i] - 1;
        while (t != start[i] - 1) {
            T[i] += distance[t];
            t++;
            if (t == N)
                t = 0;
        }
        if (T[i] < result[i])
            result[i] = T[i];
    }

    for (int i = 0; i < M; i++)
        cout << result[i] << endl;
    return 0;
}

数组一定要初始化为0！！！！
Debug费了点o(￣▽￣)ブ

Eighty Percent