PAT A1046 Shortest Distance

最近开始刷 pat!
顺带记录一下自己的沙雕行为~

题目

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:

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

Sample Output:

    3
    10
    7

代码

错误版

#include<stdio.h>

const int MAXN = 10005;

int main(void){
    int dis[MAXN];
    int N, M;
    int tot = 0;
    int a, b;
    int st;

    scanf("%d", &N);
    for(int i = 1; i<=N; i++){
        scanf("%d", &dis[i]);
        tot += dis[i];
    }

    scanf("%d", &M);
    for(int i=0; i<M; i++){
        scanf("%d%d", &a, &b);
        if(a > b){
            int x = a;
            a = b;
            b = x;
        }
        st = 0;
        while(a != b){
            st +=dis[a++];
        }
        if(st<=tot/2)
            printf("%d\n", st);
        else
            printf("%d\n", tot-st);
    }

    return 0;
}

跑完之后平台告诉我第三个测试案例段错误,我寻思着这定是数组越界,但是找了半天没有发现错误... 又过了半天...emmm 好像 MAXN 定义成了 10^4, 但是最大是 10^5!!!
orz
然后然后,平台开始说我运行超时...orz
怎么肥似!先来看看正确代码

正确代码

#include<stdio.h>

const int MAXN = 100005;

int main(void){
    int dis[MAXN], toa[MAXN];
    int N, M;
    int tot = 0;
    int a, b;
    int st;


    scanf("%d", &N);
    toa[1] = 0;
    for(int i = 1; i<=N; i++){
        scanf("%d", &dis[i]);
        tot += dis[i];
        toa[i+1] = tot;
    }

    scanf("%d", &M);
    for(int i=0; i<M; i++){
        scanf("%d%d", &a, &b);
        if(a > b){
            int x = a;
            a = b;
            b = x;
        }
        st = toa[b]- toa[a];
        if(st<=tot/2)
            printf("%d\n", st);
        else
            printf("%d\n", tot-st);
    }

    return 0;
}

so~ 总结:原程序每次查询都要累加,在极端情况下有 10^5 次操作,而一共有 10^4 次查询,所以就是 10^9 次操作,这是无法在 100ms 内完成的。而第二个程序加了 toa 数组来记录每个 exit 到第一个的距离,这样对每个查询只要计算toa[a]-toa[b],按术语来说是查询复杂度为 O(1),大大减少了查询时间。
bingo~~