关于算法复杂度

cff_0102 @ 2021-11-22 13:14:13

by cff_0102 @ 2021-11-22 13:14:46

违规zs

by 让风忽悠你 @ 2021-11-22 13:18:22

@cff_0102 可以说的再清楚一点吗

by cff_0102 @ 2021-11-22 13:20:11

@让风忽悠你 比如，

分别在 (st-x_1,st-y_1),(st-x_2,st-y_2),(st-x_3,st-y_3),......,(st-x_n,st-y_n) ，要搬到 (ed-x_1,ed-y_1),(ed-x_2,ed-y_2),(ed-x_3,ed-y_3),......,(ed-x_n,ed-y_n) 。

输出共 n 行。

第i行输出坐标为 (st-x_i,st-y_i) 的数应搬到哪个编号的位置。若输出 r ，表示 (st-x_i,st-y_i) 的椅子应搬到 (ed-x_r,ed-y_r) 。

by cff_0102 @ 2021-11-22 13:25:18

@cff_0102 （x，y）

by _ice_ @ 2021-11-22 13:55:14

你直接说题目不就行了

by cff_0102 @ 2021-11-22 14:05:36

@ice az

by Marser @ 2021-11-22 16:13:47

我只想知道这道题怎么能 O(n^2) 做

by CE_WA_TLE @ 2021-11-22 16:31:41

这怎么 O(n^2) 做

by MatrixGroup @ 2021-11-22 17:56:45

@cff_0102

我只想知道这道题怎么能 O(n^2) 做

by cff_0102 @ 2021-11-23 12:39:55

az，从第1个起始点计算从第1~n个终止点，再算第二个，……，就是有点像深搜，如果有3个货物就有：

1-1，2-2，3-3

1-1，2-3，3-2

1-3，2-2，3-1

1-3，2-1，3-2

1-2，2-1，3-3

1-2，2-3，3-1

一共6种

就是我现在只能想到按全排列整个对应算一遍——what's up,是O(n!)，有没有更简便的算法——感谢dalao指出错误（（（我是大

啊啊啊打错了