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.
Each input file contains one test case. For each case, the first line contains an integer N (in [3]), followed by N integer distances D?1?? D?2?? ? D?N??, where D?i??is the distance between the i-th and the (-st exits, and D?N?? 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 (≤), 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 1.
For each test case, print your results in M lines, each contains the shortest distance between the corresponding given pair of exits.
5 1 2 4 14 9
3
1 3
2 5
4 1
3
10
7
题意：
给出一个环形的高速公路，其中有N个出口，第Di?个出口是i到i-1的距离，而DN是N到1 的距离。给出任意两个出口，计算两者的最短距离。
题解：
显而易见，这是一个循环队列，计算距离需要考虑两个方向，但是如果直接遍历的话，时间复杂度为O(n2) O(n^2)O(n 2)这个数据量会超时（第三个测试点），所以我们需要考虑，如何优化这个距离计算过程。不妨考虑，计算每个出口两个方向的累加距离，这样计算两者之间的距离的时候，直接做加减即可，时间复杂度为O(n) O(n)O(n)。
AC代码：
#include<iostream> #include<algorithm> #include<vector> #include<queue> #include<map> #include<string> #include<cstring> using namespace std; int n; int a[100005]; int s1[100005]; int s2[100005]; int main() { cin>>n; memset(s1,0,sizeof(s1)); memset(s1,0,sizeof(s2)); for(int i=1;i<=n;i++){ cin>>a[i]; s1[i+1]=s1[i]+a[i]; } for(int i=1;i<=n;i++){ s2[i+1]=s2[i]+a[n-i+1]; } /*for(int i=1;i<=n;i++){ cout<<i<<" s1 "<<s1[i]<<endl; cout<<i<<" s2 "<<s2[i]<<endl; }*/ int m; int u,v; cin>>m; for(int i=1;i<=m;i++){ cin>>u>>v; if(u>v){ int temp=v; v=u; u=temp; } cout<<min(s1[v]-s1[u],s2[n+2-v]+s1[u])<<endl;//两个方向选最大 } return 0; }
PAT 甲级 1046 Shortest Distance (20 分)（前缀和,想了一会儿）
原文：https://www.cnblogs.com/caiyishuai/p/11456499.html