[PAT解题报告] Shortest Distance
给定一个环（高速公路），上面有n个点，每个点到下一个点的距离已知，问任意两点间的最短距离。
简单题，因为时一个环，从x到y的距离(x <
y)可以从x正向走到y，也可以从y正向走到x，两者取最小就可以了。至于距离计算可以用“前缀和”。用sum[i]表示前i个点的距离和,其实也是“原点”到达第i个点的距离，或者理解为第i个点在圆上的坐标。下标从1开始，规定sum[0]
= 0，那么x到y的距离 (x < y)可能是sum[y - 1] - sum[x - 1]，也可能是sum[n] - (sum[y
- 1] - sum[x - 1])，原因就是这是一个圈，距离可以两个方向算，总和恰好是圈长。这两者取最小就可以了。
代码：
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
int sum[100005];
int main() {
int n;
scanf("%d",&n);
for (int i = 1; i <= n; ++i) {
int x;
scanf("%d",&x);
sum[i] = x + sum[i - 1];
}
int m;
scanf("%d",&m);
for (;m;--m) {
int x,y;
scanf("%d%d",&x,&y);
int temp = sum[max(x,y) - 1] - sum[min(x,y) - 1];
printf("%d\n",min(temp, sum[n] - temp));
}
return 0;
}
原题链接： http://www.patest.cn/contests/pat-a-practise/1046
查看45道真题和解析
