一个环形公路，上面有Ｎ个站点，A1, ..., AN，其中Ai和Ai+1之间的距离为Di,AN和A1之间的距离为D0。高效的求第i和第j个站点之间的距离，空间复杂度不超过O(N)。

//点数
#define N 10

//点间距
int D[N];

//A1到每个Ai的距离
int A1ToX[N];

void preprocess() {
	srand(time(0));

	//随机分配每个点间的距离
	for (int i = 0; i < N; ++i) {
		D[i] = rand() % (RAND_MAX + 1) * N;
	}

	/*A1ToX[i]:A1到每个点Ai的距离*/
	//A1到A2的距离
	A1ToX[1] = D[1];
	for (int i = 2; i < N; ++i) {
		A1ToX[i] = A1ToX[i - 1] + D[i];
	}

	//全长
	A1ToX[0] = A1ToX[N - 1] + D[0];
}

int getDistance(int i, int j) {
	int disI = i == 0 ? 0 : A1ToX[i - 1];
	int disJ = j == 0 ? 0 : A1ToX[j - 1];
	int dis = abs(disI - disJ);
	//环形公路,每个点存在2条路径,取最短的
	return (dis > A1ToX[0] / 2) ? A1ToX[0] - dis : dis;
}

巴特西

一个环形公路，上面有Ｎ个站点，A1, ..., AN，其中Ai和Ai+1之间的距离为Di,AN和A1之间的距离为D0。高效的求第i和第j个站点之间的距离，空间复杂度不超过O(N)。

最新文章

热门文章

巴特西

一个环形公路，上面有Ｎ个站点，A1, ..., AN，其中Ai和Ai+1之间的距离为Di,AN和A1之间的距离为D0。 高效的求第i和第j个站点之间的距离，空间复杂度不超过O(N)。

最新文章

热门文章

一个环形公路，上面有Ｎ个站点，A1, ..., AN，其中Ai和Ai+1之间的距离为Di,AN和A1之间的距离为D0。高效的求第i和第j个站点之间的距离，空间复杂度不超过O(N)。