我提出了一个算法问题:
∗∗∗∗∗∗ 分布在一线的城市,请Xi。 是城市i>和P><>subi>。 人口。
现在,我们开始根据城市的距离和人口在各城市之间铺设电缆。 鉴于两个城市i和j>/i>,它们之间布设电缆的成本是<><><>X>i>-X<>/subj>>> > > ,<>>>>>,>>>P>>>>>>>> >>>>>> >。 铺设所有电缆的费用多少?
例如:
i Xi Pi - -- -- 1 1 4 2 2 5 3 3 6
然后,总费用可以计算为:
i j |Xi-Xj| max(Pi, Pj) Segment Cost - - ------ ----------- ------------ 1 2 1 5 5 2 3 1 6 6 1 3 2 6 12
因此,总费用为5+6+12=23。
虽然在O(n<><><>2)时间上可以明显做到这一点,但是在时间上却可能不太及时?
我可以考虑更快的解决办法。 如果我不错,就去O(n*logn)。 现在,根据Pi,首先让所有城市,即O(n* 标志n)。 然后,我们开始处理这些城市,以便增加Pi的顺序,原因是,你总是知道,在这种情况下,Pi(Pj) = Pi。 我们只想增加与Pi关系中的所有部分,这些部分将与较大指数挂钩,将在处理时计算。
Now the thing I was able to think of was to use several index trees in order to reduce the complexity of the algorithm. First index tree is counting the number of nodes and can process queries of the kind: how many nodes are to the right of xi in logarithmic time. Lets call this number NR. The second index tree can process queries of the kind: what is the sum of distances from all the points to the right of a given x. The distances are counted towards a fixed point that is guaranteed to be to the right of the rightmost point, lets call its x XR.Lets call this number SUMD. Then the sum of the distances to all points to the right of our point can be found that way: NR * dist(Xi, XR) - SUMD. Then all these contribute (NR * dist(Xi, XR) - SUMD) *Pi to the result. The same for the left points and you get the answer. After you process the ith point you add it to the index trees and can go on.
Edit: Here is one article about Biary index trees: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees
This is the direct connections problem from codesprint 2.
他们将在自己的网站上张贴每周解决所有问题的可行办法。
(They have said "Now that the contest is over, we re totally cool with everyone discussing their solutions to the problems.")
If I have an algorithm which is comprised of (let s say) three sub-algorithms, all with different O() characteristics, e.g.: algorithm A: O(n) algorithm B: O(log(n)) algorithm C: O(n log(n)) How do ...
I m using Electro in Lua for some 3D simulations, and I m running in to something of a mathematical/algorithmic/physics snag. I m trying to figure out how I would find the "spin" of a sphere of a ...
There s a (relatively) new sort on the block called Timsort. It s been used as Python s list.sort, and is now going to be the new Array.sort in Java 7. There s some documentation and a tiny Wikipedia ...
As a learning experience I recently tried implementing Quicksort with 3 way partitioning in C#. Apart from needing to add an extra range check on the left/right variables before the recursive call, ...
Given a 10 digit Telephone Number, we have to print all possible strings created from that. The mapping of the numbers is the one as exactly on a phone s keypad. i.e. for 1,0-> No Letter for 2->...
I have a directed graph and my problem is to enumerate all the minimal (cycles that cannot be constructed as the union of other cycles) directed cycles of this graph. This is different from what the ...
Given an array of integers arr = [5, 6, 1]. When we construct a BST with this input in the same order, we will have "5" as root, "6" as the right child and "1" as left child. Now if our input is ...
I was trying to speed up a certain routine in an application, and my profiler, AQTime, identified one method in particular as a bottleneck. The method has been with us for years, and is part of a "...
