1046 Shortest Distance （20 分）

方法1

先用数组记录前缀后，然后减去两者的差值。
由于数组形成的是个环，所以累加和是固定的，反方向的距离实际就等于总长度减去正向的长度。

#include<cstdio>
const int maxn=1e5+5;
int cost[maxn];
int dp[maxn];
int n;
void swap(int& x,int& y){
	int t=x;x=y;y=t;
}
int min(int a,int b){
	return a<b?a:b;
}
int main(){
	scanf("%d",&n);
	int sum=0;
	dp[0]=0;
	for(int i=1;i<=n;i++){
		scanf("%d",&cost[i]);
		sum += cost[i];
		dp[i]= dp[i-1]+cost[i];
	}
	int m,st,ed;
	scanf("%d",&m);
	for(int i=0;i<m;i++){
		scanf("%d%d",&st,&ed);
		if(st > ed) swap(st,ed);
		int ans =dp[ed-1] - dp[st-1];
		printf("%d\n",min(ans,sum - ans));
	}
	
	return 0;
}

方法2

有点像笨比，最后一个测试点超时了。
这里主要是记录一下如何计算循环链表或数组中的值
17分

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=1e5+5;
int cost[maxn];
int n;
void swap(int& x,int& y){
	int t=x;x=y;y=t;
}
int min(int a,int b){
	return a<b?a:b;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&cost[i]);
	}
	cost[0]=cost[n];
	int m,st,ed;
	scanf("%d",&m);
	for(int i=0;i<m;i++){
		scanf("%d%d",&st,&ed);
		if(st > ed) swap(st,ed);
		int ans1 =0;
		for(int j=st;j<ed;j++){
			ans1 +=cost[j];
		}
		int ans2 =0;
		for(int j=ed;(j+n)%n != st;j++){
			ans2 += cost[(j+n)%n];
		}
		printf("%d\n",min(ans1,ans2));
	}
	
	return 0;
}