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;
}