A29783. 环形公路出口
填空题
中等
知识点
题目描述
环形公路出口
题目描述
一条环形高速公路有N个出口，给定任意一对出口，请你算出这两个出口的最短距离。
输入
输入第一行给出区间[3,10^5]内的整数N，以及N个整数距离 D1,D2,,,,,,DN，其中Di 是第i和第i+1个出口之间的距离，DN是第N和第1个出口之间的距离。同行数字间以空格分隔。
第二行给出正整数M(≤10^4)。随后M行，每行给出一对出口的编号(出口从1到N顺序编号)。
题目保证公路全长不超过10^7。
输出
输出M行，每行给出对应输入的一对出口之间的最短距离。
输入样例
5 1 2 4 14 9
3
1 3
2 5
4 1
输出样例
3
10
7
参考答案
#include<iostream>
using namespace std;
int main(){
int s[100005]={0},n,m; //s[] 前缀和
cin>>n;
for(int i=1;i<=n;i++) {
int x;
cin>>x; //a[i]:i到i+1的距离
if(i!=n)
s[i+1]=s[i]+x; //s[i]:1到i的距离
else
s[n+1]=x; //s[n+1]存储n到1的距离
}
cin>>m; //查询次数
while(m--){
int x,y;
cin>>x>>y;
if(y<x) swap(x,y); //保证y在x后面
//s[n]-s[y]+s[n+1]+s[x]:从y到n，再从n到1，再从1到x
if(s[y]-s[x] < s[n]-s[y]+s[n+1]+s[x])
cout<<s[y]-s[x]<<endl;
else
cout<<s[n]-s[y]+s[n+1]+s[x]<<endl;
}
return 0;
}
上一题
下一题