• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

1046 Shortest Distance (20 分)

开发技术 开发技术 3小时前 1次浏览

1046 Shortest Distanc++e (20 分)

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 Spec++ification:

Each input file contains one test case. For each case, the first line contains an integer N (in [3,10的5次方]), followed by N integer distances D1 D2 ⋯ D**N, where D**i 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 107.

Output Spec++ification:

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

题意

有N个结点围成一个圈,相邻两个点之间的距离已知,且每次只能移动到相邻点。然后
给出M个询问,每个询问给出两个数字A和B即结点编号(1≤A,B≤N),求从A号结点到B
号结点的最短距离。

思路1

  • 步骤1:以dis[i]表示1号结点按顺时针方向到达“i号结点顺时针方向的下一个结点”的距离(1≤i≤N), sum表示一圈的总距离。于是对每个查询left->right,其结果就是dis(left, right)与sum-dis(left, right)中 的较小值。
  • 步骤2: dis 数组和sum在读入时就可以进行累加得到。这样对每个查询left→right,disl(ef,right)其实就是dis[right- 1]- dis[lft- 1]。这样可以做到查询复杂度为0(1)。
  • 注意点
    1. 查询的两个点的编号可能会有left > right的情况。这种情况下,需要交换left和right。
    2. 此题如果没有经过预处理dis数组和sum的做法会很容易超时。这是因为在极端情况下,每次查询都需要遍历整个数组,即有10的5次方操作,而共有10的4 次方个查询,所以极端情况会有10的9次方操作,这在100ms的时限内是不能承受的。
    3. 之所以不把dis[i]设置为1号结点按顺时针方向到达i号结点的距离,是因为N号结点到达1号结点的距离无法被这个数组所保存。

参考代码1

  1. algorithm意为”算法“,是C++的标准模版库(STL)中最重要的头文件之一,提供了大量基于迭代器的非成员模板函数。
    • 类 别 C++标准库
    • 头文件 #include <algorithm>
    • 命名空间 using namespace std
    • 其中包括以下部分函数:
      1. max()、min()和abs()
      2. swap()
      3. reverse()
      4. next_permutation()
      5. fill()
      6. sort()
      7. lower_bound()和upper_bound()
#include<cstdio>
#include<algorithm>
using namespace std;

const int MAXN = 100005;
//dis[i]表示1号节点按顺时针方向到达“i节点顺时针方向的下一个结点”的距离
//A[i]存放i号与i+1号定点的距离 
int dis[MAXN], A[MAXN]; 
int main(){
	int sum = 0, query, n, left, right; 
	scanf("%d", &n);
	for(int i =1; i <=n; i++){
		scanf("%d", &A[i]);
		sum += A[i];//累加sum 
		dis[i] = sum;//预处理dis数组 
	}
	scanf("%d", &query);
	for(int i = 0; i < query; i++){//query个查询,query就是M 
		scanf("%d%d", &left, &right);//left->right
		if(left > right) swap(left,right);//left>right时交换
		int temp = dis[right -1] - dis[left - 1];
		printf("%dn", min(temp, sum - temp)); 
	}
	return 0;
} 

思路2

转载自:PAT甲级1046-1050 – 知乎 (zhihu.com)

根据题意,各点组成一个环,使用一个数组int disto[],disto[i]表示从第一个顶点到第i个顶点顺时针经过的距离之和。例如,disto[1]为0,即第一个顶点到第一个顶点顺时针经过的距离之和,disto[2]为第一条边距离,即第一个顶点到第二个顶点顺时针经过的距离之和,disto[3]为第一条边和第二条边距离之和,即第一个顶点到第三个顶点顺时针经的距离之和。如此这般,直到disto[N]为第一条边到第N-1条边的距离之和,即第一个顶点到第N个顶点顺时针经过的距离之和,disto[N+1]为所有边的距离之和。

这样一来,如果要查询第一个顶点到第三个顶点,disto[3]得到的是顺时针距离,disto[N+1]-disto[3]得到的是逆时针的距离,取两者较小值输出。同理,查询第a个顶点到第b个顶点(默认a<b),disto[b]-disto[a]得到的是顺时针距离disto[N+1]-(disto[b]-disto[a])得到的是逆时针的距离,输出较小者。

参考代码2

#include<cstdio>
#include<algorithm>
using namespace std;

int disto[100002] = {0};

int main() {
    int N, M;
    scanf("%d", &N);
    for(int i = 2; i <= N + 1; i++)
    {
        scanf("%d", &disto[i]);
        disto[i] += disto[i - 1];//数组存储的的是累加距离
    }//累加的方式和上面一个不一样
    scanf("%d", &M);
    for(int i = 0; i < M; i++)
    {
        int a, b;//待查询的两个顶点,a<b
        scanf("%d %d", &a, &b);
        if(a > b)    swap(a, b);
        int dis = min(disto[b] - disto[a], disto[N + 1] - (disto[b] - disto[a]));
        printf("%dn", dis);
    }
    return 0;
}

思路3(柳神代码)

简单模拟。所有结点连起来会形成⼀个环形,dis[i]存储第1个结点到第i个结点的下⼀个结点的 距离,sum保存整个路径⼀圈的总和值。 求得结果就是dis[right – 1] – dis[left – 1]和 sum – dis[right – 1] – dis[left – 1]中较⼩的那⼀个~~

注意:可能left和right的顺序颠倒了,这时候要把left和right的值交换

参考3

1.c++头文件之Vector:具体用法见:c++头文件之Vector – shiff – 博客园 (cnblogs.com)

#include <iostream>
#include <vector>
using namespace std;
int main() {
	int n;
	scanf("%d", &n);
	vector<int> dis(n + 1);//带参数构造,vector数组dis有n+1个数据全为0
	int sum = 0, left, right, cnt;
	for(int i = 1; i <= n; i++) {
		int temp;
		scanf("%d", &temp);
		sum += temp;
		dis[i] = sum;
 	}
	scanf("%d", &cnt);
	for(int i = 0; i < cnt; i++) {
	scanf("%d %d", &left, &right);
	if(left > right)
	swap(left, right);
	int temp = dis[right - 1] - dis[left - 1];
	printf("%dn", min(temp, sum - temp));
	}
	return 0;
}

程序员灯塔
转载请注明原文链接:1046 Shortest Distance (20 分)
喜欢 (0)