PAT 解题报告 1046. Shortest Distance (20)

1046. Shortest Distance 题目描述:

给出一个圆, 这个圆有N各节点组成, 同时给出相邻节点之间的距离, 然后给出若干个查询, 要求输出任意两个节点之间的最短距离.

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.

1046. Shortest Distance 算法分析:

简单题, 线性扫一遍, 求出每个节点到零节点的距离, 那么节点a, b之间的距离就是他们到零节点距离的差值, 因为是圆, 所以最短距离要么是这个差值要么就是整个圆的长度减去这个差值, 也就是顺时针从a到b还是逆时针从a到b之间取一个较小的值即可, AC代码如下:

#include <iostream>
#include <fstream>
#include <sstream>

#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>

#include <algorithm>
#include <string>
#include <vector>

#define REP(i,n) for(int i=0;i<(n);++i)
using namespace std;

int main(void) {
    int N, M;
    int dist[100005];
    cin>>N;
    REP(i, N) cin>>dist[i];
    cin>>M;
    int tot = 0;
    int distFromZero[100005];
    memset(distFromZero, 0, sizeof(distFromZero));
    distFromZero[1] = dist[0];
    REP(i, N) {
        distFromZero[i+1] = dist[i] + distFromZero[i] ;
        tot += dist[i];
    }

    int a, b;
    int c;
    REP(i, M) {
        cin>>a>>b;
        if(a > b) {
            c = a;
            a = b;
            b = c;
        }
        a--;
        b--;
        int di = distFromZero[b] - distFromZero[a];
        cout<<min(di, tot-di)<<endl;
    }
    return 0;
}
Written on January 19, 2014