首页 › 题库 › C/C++编程考级 › C/C++编程三级 › 简答题
简答题 偏难
#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 &lt;iostream&gt; #include &lt;algorithm&gt; #include &lt;vector&gt; using namespace std; int main() {     int N;     cin &gt;&gt; N;     vector&lt;int&gt; distances(N);     for (int i = 0; i &lt; N; ++i) {         cin &gt;&gt; distances[i];     }     vector&lt;int&gt; prefixSum(N + 1, 0);     for (int i = 0; i &lt; N; ++i) {         prefixSum[i + 1] = prefixSum[i] + distances[i];     }     int M;     cin &gt;&gt; M;     for (int i = 0; i &lt; M; ++i) {         int start, end;         cin &gt;&gt; start;         cin &gt;&gt; end;         if (start &gt; end) {             swap(start, end);         }         int sum = prefixSum[end - 1] - prefixSum[start - 1];         int total = prefixSum.back();         cout &lt;&lt; min(sum, total - sum) &lt;&lt; endl;     }     return 0; }</pre>
这道题暂未补解析。