1046. Shortest Distance (20)

1. 原题： https://www.patest.cn/contests/pat-a-PRactise/1046

2. 思路：

3. 源码（已AC）：

#include<iostream>#include<algorithm>//使用min，max函数#include<vector>using namespace std;int main(void){	//freopen("in.txt", "r", stdin);	int N, total = 0;	scanf("%d", &N);	vector<int> ev(N + 1, 0);//保存两点间的距离	vector<int> acc(N + 1, 0);//保存起点到当前点的距离	for (int i = 1; i <= N; i++)	{		acc[i] = total;		scanf("%d", &ev[i]);		total += ev[i];	}	int M, sta, end;//分别为所求问题个数， 起始点，末点。	int lnum, gnum;//分别表示两点较小的和较大的序号	scanf("%d", &M);	for (int i = 0; i < M; i++)	{		scanf("%d %d", &sta, &end);		lnum = min(sta, end);		gnum = max(sta, end);		int sum = acc[gnum] - acc[lnum];		int min_dist = sum > (total / 2) ? (total-sum) : sum;		printf("%d/n", min_dist);	}	return 0;}