AcWing 1530. 最短距离
原题链接
简单
作者:
magpie
,
2021-01-03 15:18:05
,
所有人可见
,
阅读 398
//请务必注意,第一行第一个数是个数,别看错了
//思路:很直观,就是查询,查询也就两个结果,一种是正向,一种是反向,反向和正向的关系就是,其和为总的distance
//那么,用什么方法查询呢? : 通过模拟过程,发现查询的结果就是a-b 之间的距离和, 很像前缀和,所以使用前缀和查询
#include<iostream>
using namespace std;
const int N=1e5+10;
int d[N];
int sum[N];
int all=0;
int main(){
int n;
cin>>n; //先放进来,防止忘记
for(int i=1;i<=n;i++) {
cin>>d[i];
all+=d[i];
}
for(int i=1;i<=n;i++)sum[i]=sum[i-1]+d[i];
int q,a,b;
int res;
cin>>q;
while(q--){
cin>>a>>b;
int t=abs(sum[b-1]-sum[a-1]);
res=min(t,all-t);
cout<<res<<endl;
}
return 0;
}