PAT甲级 1046 Shortest Distance (20分) （题目 + 代码 + 详细注释 + 最后一个测试点超时分析）
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 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
//本题题意是有n个点围一个圈，求任意两点之间的最小距离，为何有最小距离呢？因为在环上从a -> b，可以顺时针，也可逆时针，所走的路程可能不一样。求法就比较简单了，可以按顺时针（逆时针也可）求出距离，和圆的周长的一半比较，若小于周长的一半，则这个距离即为所求，否则就是周长减去该距离。这是最简单的模拟，但是如果你每次得到两个点时，都一个个的把距离加起来再比较，要注意到题目中数据是n最大1e5，m最大1e4，会超时的（我就踩过坑）。处理办法是在读入Di时，同时求出第（i + 1）个点到初始点（1号）的距离dis[i + 1]，在求a -> b 的距离时，只需算出 dis[b] - dis[a]即可，就是O（1）的复杂度了，不会超时了。下面是两种代码：
法一：结果超时
#include
#include
using namespace std;
int a[100005];
int main() {
int n, sum = 0;
scanf("%d", &n);
for (int i = 1; i y) //默认是（x, y），所以当读入的x > y时，就交换x， y
swap(x, y); //初用C++，原来algorithm头文件里面有swap函数，就不用自己写了
int sum0 = 0; //sum0是x -> y的距离，初始为0
for (int i = x; i < y; i++)
sum0 += a[i];
printf("%d\n", sum0 < k ? sum0 : sum - sum0);
}
return 0;
}
//法二：AC了
#include
#include
using namespace std;
int a[100005], dis[100005]; //dis记录每个点到初始点(1号)的距离
int main() {
int n, sum = 0;
scanf("%d", &n);
for (int i = 1; i y)
swap(x, y)
int sum0 = dis[y] - dis[x]; //直接求出两点之间的距离
printf("%d\n", sum0 < k ? sum0 : sum - sum0);
}
return 0;
}
作者：呆码农梦中识bug，程序员哭求加工资
