我在interviewStreet网上找到了一个谜题,并尝试按如下方式解决:
有一个无限的整数网格,N人有他们的房子。 他们决定团结在一个共同的聚会场所,这是一个人的家。 从任何给定的小区,所有8个相邻小区在1个单位时间内可达。 例如:(x,y)可以在一个单位时间内从(x-1,y + 1)到达。 找到一个共同的会面地点,最大限度地减少所有人的旅行时间总和。
我首先想到的是及时编写n²复杂度的解决方案,但约束条件是
1 <= N <= 10 ^ 5并且输入中每个坐标的绝对值将至多为10 ^ 9
所以,我改变了我的第一种方法,而不是考虑距离和旅行时间的问题,我把不同的房子看作不同的身体,不同的重量。 而不是计算所有距离,我寻找这组物体的重心。
这是我的“求解”函数的代码,vectorToTreat是一个lengthX2表,存储有关网格上各点的所有数据,结果是打印到stdout的数字:
long long solve(long long** vectorToTreat, int length){ long long resul = 0; int i; long long x=0; long long y=0; int tmpCur=-1; long long tmp=-1; for(i=0;i<length;i++){ x+=vectorToTreat[i][0]; y+=vectorToTreat[i][1]; } x=x/length; y=y/length; tmp = max(absol(vectorToTreat[0][0]-x),absol(vectorToTreat[0][1]-y)); tmpCur = 0; for(i=1;i<length;i++){ if(max(absol(vectorToTreat[i][0]-x),absol(vectorToTreat[i][1]-y))<tmp){ tmp = max(absol(vectorToTreat[i][0]-x),absol(vectorToTreat[i][1]-y)); tmpCur = i; } } for(i=0;i<length;i++){ if(i!=tmpCur) resul += max(absol(vectorToTreat[i][0]-vectorToTreat[tmpCur][0]),absol(vectorToTreat[i][1]-vectorToTreat[tmpCur][1])); } return resul; }
现在的问题是我通过了12个官方测试案例超过13个,我不知道我做错了什么想法? 提前致谢。 AE
这个问题的关键是一组点的质心概念。 会议地点是代表所有房屋的一组点的质心最近的房子。 使用这种方法,您可以在线性时间内解决问题,即O(N)。 我在Python中完成了它,提交了我的解决方案并通过了所有测试。
但是,很容易构建质心方法不起作用的数据集。 这是一个例子:
[(0, 0), (0, 1), (0, 2), (0, 3), (1, 0), (1, 1), (1, 2), (1, 3), (2, 0), (2, 1), (2, 2), (2, 3), (3, 0), (3, 1), (3, 2), (3, 3), (101, 101)]
最好的解决方案是在(2,2)的房子会议,成本是121(你可以通过详尽的搜索找到它 – O(N ^ 2))。 但是,质心方法会产生不同的结果:
网站上的测试用例显然是以质心解决方案正常的方式塑造的,或者他们只是想知道你是否知道质心的概念。
我没有阅读您的代码,但请考虑以下示例:
重心位于(2,0),总行程时间最短为8,但最佳解决方案为(3,0),总行程时间最短为7。
您好,感谢您的回答和评论,他们非常乐于助人。 我终于放弃了使用重心的算法,当我在其上运行一些样本时,我注意到当房屋聚集在不同村庄时,它们之间的距离不同,算法不起作用。 如果我们考虑@Rostor上面所说的例子:
(0,0),(1,0),(2000,0),(3000,0),(3001,0),(3002,0),(3003,0)
使用重心的算法回答第三宫是解决方案,但正确的答案是第四宫。 在这种问题中使用的正确概念是中位数,并使其适应所需的维度。 这是一篇很棒的文章,谈论几何中位数 ,希望它有所帮助。
解:
“……这是某人的房子”意味着你选择一个被占用的房子,而不是一个任意的位置。
编辑 :oops,max(abs(aA),abs(bB))替换(abs(aA)+ abs(bB))。 当p-> infinty时,请参阅L_p空格以获取更多详细信息。
从(a,b)到(A,B)的距离是max(abs(aA),abs(bB))。 蛮力的方式是计算每个被占用房屋的总出行时间,跟踪到目前为止最好的会面地点。
可能还要等一下。 质心中心排序可以允许您确定搜索顺序的优先级。 我看到你正在使用这个指标的良好质心计算:采用第一个坐标的简单平均值和第二个成分的简单平均值。
如果您对距离函数有所了解,可以得到(x1,y1)和(x2,y2)之间的旅行时间
def dist( (x1,y1), (x2,y2)): dx = abs(x2-x1) dy = abs(y2-y1) return max(dx, dy)
如果在带有网格的纸张上绘制草图,则可以看到。
因此,您只需要遍历每个房子,总结其他房屋的旅行时间,并以最低金额购买房屋。
完整的解决方案是
houses = [ (7,4), (1,1), (3,2), (-3, 2), (2,7), (8, 3), (10, 9) ] def dist( (x1, y1), (x2, y2)): dx = abs(x1-x2) dy = abs(y1-y2) return max(dx, dy) def summed_time_to(p0, houses): return sum(dist(p0, p1) for p1 in houses) distances = [ (summed_time_to(p, houses), i) for i, p in enumerate(houses) ] distances.sort() min_dist = distances[0][0] print "best houses are:" for d, i in distances: if d==min_dist: print i, "at", houses[i]
我在scala中编写了一个快速且脏的网格距离测试器,它将平均值与穷举搜索的最小值进行比较:
class Coord (val x:Int, val y: Int) { def delta (other: Coord) = { val dx = math.abs (x - other.x) val dy = math.abs (y - other.y) List (dx, dy).max } override def toString = " (" + x + ":" + y + ") " } def run (M: Int) { val r = util.Random // reproducable set: // r.setSeed (17) val ucells = (1 to 2 * M).map (dummy => new Coord (r.nextInt (M), r.nextInt (M))).toSet take (M) toSeq val cells = ucells.sortWith ((a,b) => (ax < bx || ax == bx && ay <= by)) def distanceSum (lc: Seq[Coord], cell: Coord) = lc.map (c=> cell.delta (c)).sum val exhaustiveSearch = for (x <- 0 to M-1; y <- 0 to M-1) yield (distanceSum (cells, new Coord (x, y))) def sum (lc: Seq[Coord]) = ((0,0) /: lc) ((a, b) => (a._1 + bx, a._2 + by)) def avg (lc: Seq[Coord]) = { val s = sum (lc) val l = lc.size new Coord ((s._1 + l/2) / l, (s._2 + l/2) / l) } val av = avg (ucells) val avgMethod = distanceSum (cells, av) def show (cells : Seq[Coord]) { val sc = cells.sortWith ((a,b) => (ax < bx || ax == bx && ay <= by)) var idx = 0 print ("t") (0 to M).foreach (i => print (" " + (i % 10))) println () for (x <- 0 to M-1) { print (x + "t") for (y <- 0 to M -1) { if (idx < M && sc (idx).x == x && sc (idx).y == y) { print (" x") idx += 1 } else if (x == av.x && y == av.y) print (" A") else print (" -") } println () } } show (cells) println ("exhaustive Search: " + exhaustiveSearch.min) println ("avgMethod: " + avgMethod) exhaustiveSearch.sliding (M, M).toList.map (println) }
这是一些示例输出:
run (10) 0 1 2 3 4 5 6 7 8 9 0 0 - x - - - - - - - - 1 - - - - - - - - - - 2 - - - - - - - - - - 3 x - - - - - - - - - 4 - x - - - - - - - - 5 - - - - - - x - - - 6 - - - - A - - x - - 7 - xx - - - - - - - 8 - - - - - - - - - x 9 x - - - - - - - - x exhaustive Search: 36 avgMethod: 37 Vector(62, 58, 59, 60, 62, 64, 67, 70, 73, 77) Vector(57, 53, 50, 52, 54, 57, 60, 63, 67, 73) Vector(53, 49, 46, 44, 47, 50, 53, 57, 63, 69) Vector(49, 46, 43, 41, 40, 43, 47, 53, 59, 66) Vector(48, 43, 41, 39, 37, 37, 43, 49, 56, 63) Vector(47, 43, 39, 37, 36, 37, 39, 46, 53, 61) Vector(48, 43, 39, 36, 37, 38, 40, 43, 51, 59) Vector(50, 44, 40, 39, 38, 40, 42, 45, 49, 57) Vector(52, 47, 44, 42, 42, 42, 45, 48, 51, 55) Vector(55, 52, 49, 47, 46, 47, 48, 51, 54, 58)
平均值并不总是最佳位置(如本例所示),但您可以跟随具有更高或更好价值的邻居,找到最佳位置。 这是一个很好的起点,我在下面找到了一个局部最优样本,你会陷入困境。 这对于庞大的数据集来说非常重要。
但我没有certificate这是否总是如此,以及如何直接找到完美的位置。
这就是我所做的
def abs(a) (a < 0) ? -a : a end # Calculate distance between cell(i) to cell(j) # # a and b are point structures each having x, y co-ordinate def dist(a, b) if ((a[0] == b[0]) && (a[1] == b[1])) return 0 end del_row = abs(a[0] - b[0]) del_col = abs(a[1] - b[1]) if (del_row == del_col) return del_row else return del_row > del_col ? del_row : del_col end end # Find the median cell from an array of cells def find_median(array) # If array is of even length, the median element is not in the array. We've to consider # two adjacent elements of the median. For odd case we've just one median n = array.length # Median finding can be done at O(n)... # # Sort cell array - O(nlogn) array = array.sort do |cell1, cell2| # Try first by comparing x if (cell1[0] != cell2[0]) cell1[0] < cell2[0] ? -1 : 1 else # Resolve tie by comparing y cell1[1] <=> cell2[1] end end # Find median k = n / 2 median_element = [] if ((n % 2) == 0) median_element << array[k] median_element << array[k+1] else median_element << array[k] end median_element end # Calculate travel time given an array of cells and a cell indicating the meeting point def calculate_travel_time(array, meeting_cell) travel_time = 0 array.each do |cell| # Skip the meeting cell itself if (!((cell[0] == meeting_cell[0]) && (cell[1] == meeting_cell[1]))) travel_time = travel_time + dist(cell, meeting_cell) end end travel_time end def figure_out_the_meeting_point(array) if (array.nil?) return 0 end n = array.length if (n == 0) return 0 end if (n == 1) # Lonely person return 0 end if (n == 2) # Just two neighbors return dist(array[0], array[1]) end # Find median median = find_median(array) median_length = median.length min_travel_time = 0 meeting_point = nil if (median_length == 1) min_travel_time = calculate_travel_time(array, median[0]) meeting_point = median[0] else # We've two candidates. Need to check minimum of them t_first_median = calculate_travel_time(array, median[0]) t_second_median = calculate_travel_time(array, median[1]) if (t_first_median < t_second_median) min_travel_time = t_first_median meeting_point = median[0] else min_travel_time = t_second_median meeting_point = median[1] end end return min_travel_time, meeting_point end # Handle STDIN and STDOUT for I/O def handle_io() STDOUT.flush n = gets.to_i array = [] (n).times do STDOUT.flush s = gets array << s.split(' ').map(&:to_i) end array end tt, mp = figure_out_the_meeting_point(handle_io) puts tt puts mp
网格是无限的。 因此,解决方案应该是整数溢出安全的。 我已经检查了大量的int并且Ruby正确地按照预期将它们转换为BigNum。
知道为什么我没有通过所有测试用例。
我尝试使用几何中位数的方法来解决这个问题。 但13个测试用例中只有11个通过。 这是我的策略。
1. finding centroid of a set of points. 2. then found the point closest to that centroid.
我甚至试过但只通过了13个测试用例中的4个。 他们说,分段故障。
但我已经制作了两个100001的数组,并使用了一些变量。
我的算法。
找到给定点的质心。
找到最靠近质心的点。 使用最大值(abs(aA),abs(bB))得到所有距离的总和。
需要了解更多c/c++开发分享所有旅行时间的最小总和,也可以关注C/ C++技术分享栏目---计算机技术网(www.ctvol.com)!
以上就是c/c++开发分享所有旅行时间的最小总和相关内容,想了解更多C/C++开发(异常处理)及C/C++游戏开发关注计算机技术网(www.ctvol.com)!)。
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/980222.html