请教一个算法题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

请教一个算法题

请教一个算法题# JobHunting - 待字闺中

y*r2015-06-12 07:06

1 楼

Dear Customer
We regret to let you know that we cancelled your open order number on
Amazon.com because it violates our Condition of Use.
Specifically, your order violates our quantity restrictions.
At this point, we are only canceling your order, but if you continue to
violate Amazon.com policies, we may take further action, including closing
your Amazon.com account.

c*t2015-06-12 07:06

2 楼

两排各有N个node: A[1-N], B[1-N], 相邻两个node都相连，给weight a[0~N-1], b[0~
N-1]. 下图中 a=[1,8,8,1], b=[5,2,2,5] . 竖着连接K(K>=1)条edge，只能对应的
node相连(ie. A1连B1， A4连B4），这样任意两个node都有一条最短path，取所有最
短path的最大值为diameter。给予 N 和 K，求如何连接可以得到最小diameter。
A1--1--A2--8--A3--8--A4--1--A5
B1--5--B2--2--B3--2--B4--5--B5
test case 1 如上图 N = 5, K = 2, a = [1,8,8,1], b = [5,2,2,5], 最优解连A2-B2
和A4-B4
请教如何解？

t*r2015-06-12 07:06

3 楼

难怪能一直活着啊

【在 y***r 的大作中提到】

: Dear Customer
: We regret to let you know that we cancelled your open order number on
: Amazon.com because it violates our Condition of Use.
: Specifically, your order violates our quantity restrictions.
: At this point, we are only canceling your order, but if you continue to
: violate Amazon.com policies, we may take further action, including closing
: your Amazon.com account.

b*a2015-06-12 07:06

4 楼

最简单的情况 K=2
那就是要在所以子线段中找一段A和B的权重相差最多的假设相差x
这样所以的最短径都缩短了x Diameter也减小了x
必须是选权重相差最多的一段因为如果选了次多的把次多替换成最多的一段总是可以
把diameter再减小
以此类推如果K就偶数就依次选最多的一段次多的一段第三多的一段
选权重相差最多的子段先把AB权重相减在等到的数组里找和最大的子数组是不是很
熟悉
但是K为奇数的时候好像更麻烦一点没想清楚谁来解答一下

c*n2015-06-12 07:06

5 楼

估计班上大部分账号已经挂了，能买出来算幸运的。

b*a2015-06-12 07:06

6 楼

好像还忽略了同侧的点的最短路径问题 orz

l*r2015-06-12 07:06

7 楼

shipping soon了之后Amazon是不是就不管了？

m*n2015-06-12 07:06

8 楼

呵呵，刚注册了10个账号，都是shipping soon.

c*n2015-06-12 07:06

9 楼

嗯，但会秋后算账

【在 l*******r 的大作中提到】

: shipping soon了之后Amazon是不是就不管了？

g*n2015-06-12 07:06

10 楼

怎么算。。

【在 c*****n 的大作中提到】

: 嗯，但会秋后算账

c*n2015-06-12 07:06

11 楼

过几天热门的东西会in不了,所以早死往往死里in

【在 c*****n 的大作中提到】

: 嗯，但会秋后算账

s*02015-06-12 07:06

12 楼

注册了一个帐号，也在ship了

l*32015-06-12 07:06

13 楼

牛人啊

【在 m***n 的大作中提到】

: 呵呵，刚注册了10个账号，都是shipping soon.

h*e2015-06-12 07:06

14 楼

BL以后shipping soon的也能寄出来。我发现我下单instant cancel之后，帐号里的
shipping soon的kinect还是全部寄出来了，但是没办法下新的了。

【在 l*******r 的大作中提到】

: shipping soon了之后Amazon是不是就不管了？

n*l2015-06-12 07:06

15 楼

是不是这个地址都不行了？

【在 y***r 的大作中提到】

S*22015-06-12 07:06

16 楼

我的账户应该能行，还没从AMZ买过Kinect呢

k*r2015-06-12 07:06

17 楼

wk,你们是真的不能下还是假的啊,又下了30个,你们不是在忽悠别人下自己不下吧.....
............................................................................
..................

【在 y***r 的大作中提到】