C/C++教程

1046 Shortest Distance (20 分)

本文主要是介绍1046 Shortest Distance (20 分),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

1. 题目

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 (≤10^4), 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 10^7.

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

2. 题意

有一条环形公路上n个站点,题目给出了相邻两个站点之间的距离,计算任意两个站点之间的最短距离。

3. 思路——前缀和

  1. 创建两个数组:dist中表示i到i+1的距离;sum为前缀和,表示从1到i的距离。

img

  1. 计算两个站点之间距离,两个站点分别为x,y;这里保证x<y(判断大小,如果x>y,则两个数交换即可),然后计算”x到y的距离“和“y到x的距离”:
    1. (x到y的距离)=(1到y的距离sum[y])-(1到x的距离sum[x])
    2. (y到x的距离)=(y到n的距离sum[n]-sum[y])+(y到1的距离dist[y])+(1到x的距离dist[x])
  2. 比较(x到y的距离)和(x到y的距离),两个中的较小值为x和y之间的最短距离。

4. 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

int main()
{
	LL n;
	cin >> n;
	LL dist[n + 1];	// 表示从i到(i+1)的距离 
	LL sum[n + 1];	// 前缀和,表示从1到i的距离
	memset(dist, 0, sizeof dist);
	memset(sum, 0, sizeof sum);
	for (int i = 1; i <= n; ++i)
	{
		cin >> dist[i];
		// 前缀和计算,(1到i的距离)=(1到i-1的距离)+(i-1到i的距离) 
		sum[i] += sum[i - 1] + dist[i - 1];
	}
	
	int m;
	cin >> m;
	int x, y;
	for (int i = 0; i < m; ++i)
	{
		cin >> x >> y;
		if (x > y) swap(x, y);	// 如果x坐标大于y,则交换两个数
		// x到y的距离 
		int dist1 = sum[y] - sum[x];
		// y到x的距离(因为公路为循环)=(y到n的距离)+(y到1的距离dist[n])+(1到x的距离sum[x]) 
		int dist2 = sum[n] - sum[y] + dist[n] + sum[x];
		// 判断(x到y的距离)和(y到x的距离)大小,输出距离较小值 
		cout << (dist1 < dist2 ? dist1 : dist2) << endl;
	}
	return 0;
} 
这篇关于1046 Shortest Distance (20 分)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!