1046. Shortest Distance (20)

​ 时间限制

​ 100 ms

​ 内存限制

​ 65536 kB

​ 代码长度限制

​ 16000 B

​ 判题程序

​ Standard

​ 作者

​ CHEN, Yue

The task is really simple: given N exits on a highway which forms a simple cycle, you are supposed to tell the shortest distance between any pair of exits.

Input Specification:

Each input file contains one test case. For each case, the first line contains an integer N (in [3, 105]), followed by N integer distances D1 D2 … DN, where Di is the distance between the i-th and the (i+1)-st exits, and DN is between the N-th and the 1st exits. All the numbers in a line are separated by a space. The second line gives a positive integer M (<=104), with M lines follow, each contains a pair of exit numbers, provided that the exits are numbered from 1 to N. It is guaranteed that the total round trip distance is no more than 107.

Output Specification:

For each test case, print your results in M lines, each contains the shortest distance between the corresponding given pair of exits.

Sample Input:

5 1 2 4 14 9
3
1 3
2 5
4 1

Sample Output:

3
10
7

最开始利用循环算sum；最后一个测试点过不去；然后想到把前面的每一个的和均加在一起，最后求两个值得时候就变成加减法运算了，suma=sum[max-1]-max[min-1]; sumb=sum[min-1]+sum[sum.size()-1]-sum[max-1];

然后最短距离便出来了

代码如下：

#include<iostream>
#include<vector>
using namespace std;


int main(){
	int n;
	scanf("%d",&n);
	vector<int> v(n+1);
	vector<int> sum(n+1);
	for(int i=1;i<=n;++i){
		scanf("%d",&v[i]);
		if(i==1)sum[i]=v[i];
		else{sum[i]+=sum[i-1]+v[i];}
	}
	int m,a,b;
	scanf("%d",&m);
	for(int i=0;i<m;++i){
		scanf("%d%d",&a,&b);
		if(a==b){
			printf("0\n");
			continue;
		}
		int suma=0,sumb=0;
		
		int min,max;
		if(a<b){
			min=a;
			max=b;
		}else{
			min=b;
			max=a;
		}
		suma=sum[max-1]-sum[min-1];
		sumb+=sum[min-1]+sum[sum.size()-1]-sum[max-1];
		if(suma<=sumb){
			printf("%d\n",suma);
		}else{
			printf("%d\n",sumb);
		}
	}
	return 0;
}