PAT甲级 1046题号

想法

这道题目第一眼看上去我以为是直接每次循环查找就可以了，但是后面发现200ms的时间限制和很大的出口数量，所以后面用了一维的前缀和的方法。

题面

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 D1 D2 ⋯ DN , where Di 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 (≤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
结尾无空行

代码

数组的含义是从第一个出口到当前下标出口的距离，只要相互减一下就可以得到任意两个出口在从1到N出口方向上的距离，再通过总距离比较反向的距离即可。

#include <iostream>
using namespace std;

//非常接近前缀和的题
//第一眼以为普通模拟就能搞定，但是整个问题可以缩小到O(N + M)的程度
//以第一个出口为起点,用数组记录第一个出口到当前下标出口的总距离
const int MAX_N = 100010;
int exits[MAX_N];

int main()
{
    int N, total = 0;
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        int dis;
        cin >> dis;
        exits[i] = total;
        //记录总的一圈的距离，这很重要
        total += dis;
    }

    int M;
    cin >> M;
    for (int i = 0; i < M; i++)
    {
        int f, d;
        cin >> f >> d;
        //方便计算如果是逆过来的数，就直接交换一下
        if (f > d)
        {
            int temp = d;
            d = f;
            f = temp;
        }
        //可以在O（1）时间内算出从d到f的距离
        int pos = exits[d] - exits[f];
        //比较反向一圈的距离和当前距离，输出小的那个
        cout<<min(pos, total - pos)<<endl;
    }
    return 0;
}