某startup的代码题

发信人: jingi08 (求驴骑), 信区: JobHunting
标  题: 某startup的代码题
发信站: BBS 未名空间站 (Tue Sep 16 19:41:47 2014, 美东)

要求给出最优解法，但我想了半天也没进展。。

从A点传送字节去B点，求最短的传送时间。

input：
N: 最需传送的总字节数
L: 建立连接所需时间。 例如 L = 5s， 那么从A传一次到B建立连接所需时间为 2 * L
= 10s，传2次的话就需建立2次连接，那就是 2 * (2 * L) = 20s
B: 字节传送速率
C: block个数
接下来是C行，每行两个数 start, end 表示block里起始和中止位置。 例如： 2， 10
, 表示需要传送从位置2到9的字节，一共8个字节数

例子1：
input：
N = 2000,
L = 15,
B = 10;
C = 7;
0, 200
200, 400
400, 600
600, 800
800, 1000
1000, 2000
0, 1800

output: 340
这个例子里，因为建立连接时间过大。所以直接传送最大的两个block (0, 1800), (
1000, 2000) 所需时间最少，340

例子2：
N = 2000,
L = 5,
B = 10;
C = 7;
0, 200
200, 400
400, 600
600, 800
800, 1000
1000, 2000
0, 1800


output: 260
这个例子和上一个唯一不同是 L = 5，连接时间很小。所以传送小block反而节省时间
。 (0, 200), (200,400),(400,600),(600,800),(800,1000),(1000,2000)，总时间是
260.

限值如下：
1 <= N, L, B < 2^32
1 <= C <= 100000

要求给出最优算法。

--
※ 修改:·jingi08 於 Sep 16 19:42:10 2014 修改本文·[FROM: 128.]
※ 来源:·WWW 未名空间站 网址：mitbbs.com 移动：在应用商店搜索未名空间·[FROM: 128.]

http://www.mitbbs.com/article_t/JobHunting/32784183.html

FT中文十大 华尔街中文十大 水木十大 小百合十大 饮水思源十大 日月光华十大

序柔系列睡衣反季优惠39元睡衣赠5元京券更有秋冬新款特惠 ， 更多京东优惠券