[C++知识库](3.1E)Shortest Distance (20)

题目：

?样例：

?这道题我最开始写的代码在更正过一些小问题后如下：

#include<stdio.h>
int main(){
    int n,m;
    int b,e;
    int d[2][10000]={0};
    int min[10000];
    scanf("%d",&n);
    int a[100000];
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    scanf("%d",&m);
    for(int i=0;i<m;i++){
        int t;
        scanf("%d%d",&b,&e);
        if(b>e){
            t=e;
            e=b;
            b=t;
        }
        int l=b;
        while(l<e)
            d[0][i]+=a[l++];//这里不可以直接b++因为会把b的值改了影响到后面   
        int j=1;
		int r=e;    
        while(j<b)
            d[1][i]+=a[j++];
        while(r<=n)
            d[1][i]+=a[r++];           
        if(d[0][i]<d[1][i])
            min[i]=d[0][i];
        else
            min[i]=d[1][i];
        //printf("%d  %d\n",d[0][i],d[1][i]);//这里把d到e和e到b的距离都输出来发现d[1][i]永远是30
        printf("%d\n",min[i]);
        }
    return 0;
}

如果只追求一个运行的答案的话，上面这样完全没有问题，但如果在答案正确的同时还满足运行时限的要求，就要从时间复杂度这个角度来理解一下，如下是我的御用大佬给出的解释：

?

?所以很明显，我最初的代码时间复杂度过高。那要如何改进呢，我新学习到了两个词语：前缀与差分，对于多层循环的问题我们可以通过技巧来减少循环：

详细可以参考：(3条消息) 前缀和与差分 图文并茂 超详细整理（全网最通俗易懂）_林深不见鹿 的博客-CSDN博客_前缀和和差分

于是改进后的代码如下：

#include<stdio.h>
int main(){
	int n,m;
	scanf("%d",&n);
	int d[100000];
	int b[10000],e[10000];
	int sum=0;
	for(int i=1;i<=n;i++){
		scanf("%d",&d[i]);
		sum+=d[i];
	}
	int dis[100000];
	for(int i=2;i<=n;i++)
		dis[i]=dis[i-1]+d[i-1];//这个式子可以省去一个循环嗷 
	scanf("%d",&m);
	for(int i=0;i<m;i++){
		scanf("%d%d",&b[i],&e[i]);
		int t;
		if(b[i]>e[i]){
			t=e[i];
			e[i]=b[i];
			b[i]=t;
		}
		int dis0=dis[e[i]]-dis[b[i]];
		if(dis0<(sum-dis0))
			printf("%d\n",dis0);
		else
			printf("%d\n",sum-dis0);
	}
	return 0;
}