思路:
1. 题意为输入点数以及点之间的距离,要求给出点对,输出点之间的最短距离。
2. 处理时确定点对的大小顺序,分别计算从小到大的和sum1,以及从大到小的和sum2,之后对两数进行比较,确定较小的数并输出。代码如下
#include<cstdio>
int a[100010];
int p1[10010];
int p2[10010];
int shortest_way(int n,int c,int b){int sum1=0,sum2=0,i;int low,high;low=c<b?c:b;high=c>b?c:b;for(i=low-1;i<high-1;i++){sum1+=a[i];}for(i=high-1;i<n;i++){sum2+=a[i];}for(i=0;i<low-1;i++){sum2+=a[i];}return sum1<sum2?sum1:sum2;
}
int main(){int N,i,M;scanf("%d",&N);for(i=0;i<N;i++){scanf("%d",&a[i]);}scanf("%d",&M);for(i=0;i<M;i++){scanf("%d%d",&p1[i],&p2[i]);}for(i=0;i<M;i++){printf("%d\n",shortest_way(N,p1[i],p2[i]));}
}
提交时第三个测试点出现超时现象,这里循环时间太大出现了超时,因此必须经过预处理,但不太清楚如何进行预处理,查看答案后发现,实例中为一个环,因此sum1和sum2之和为环的总长度,初始化时一定是要预先将查询值存在数组里面,在输入时进行预处理,确定一个点1,然后将1到个点的距离存储在数组中,查询i,j点时只需将数组中对应位置元素相减即可,在输出时确定两者之间的较小值。
总结:没有想到的原因是没有注意到整体结构是个圆环状,因此计算了两边的距离。此外,没有注意到可以将两点之间的距离转换为求一个确定点到两点之间的距离之差。