简答题
偏难
#7535
环形公路出口 一条环形高速路上有 N 个出口。给定任意一对出口,请你算出这两个出口之间的最短距离。 时间限制:1000 内存限制:65536 输入 输入第一行给…
环形公路出口
一条环形高速路上有 N 个出口。给定任意一对出口,请你算出这两个出口之间的最短距离。
时间限制:1000
内存限制:65536
输入
输入第一行给出区间 [3,105] 内的整数 N,以及 N 个整数距离 D1 D2 … DN,其中 Di 是第 i 和第 i+1 个出口之间的距离,DN 是第 N 和第 1 个出口之间的距离。同行数字间以空格分隔。 第二行给出正整数 M (≤ 104)。随后 M 行,每行给出一对出口的编号(出口从 1 到 N 顺序编号)。题目保证公路全长不超过 107。
输出
输出 M 行,每行给出对应输入的一对出口之间的最短距离。
样例输入
5 1 2 4 14 9 3 1 3 2 5 4 1
样例输出
3 10 7
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
int N;
cin >> N;
vector<int> distances(N);
for (int i = 0; i < N; ++i) {
cin >> distances[i];
}
vector<int> prefixSum(N + 1, 0);
for (int i = 0; i < N; ++i) {
prefixSum[i + 1] = prefixSum[i] + distances[i];
}
int M;
cin >> M;
for (int i = 0; i < M; ++i) {
int start, end;
cin >> start;
cin >> end;
if (start > end) {
swap(start, end);
}
int sum = prefixSum[end - 1] - prefixSum[start - 1];
int total = prefixSum.back();
cout << min(sum, total - sum) << endl;
}
return 0;
}</pre>
这道题暂未补解析。