瑞士空军v5:因处于下班时间未护航被劫客机 (转载)# Joke - 肚皮舞运动
j*8
1 楼
要求给出最优解法,但我想了半天也没进展。。
从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
要求给出最优算法。
从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
要求给出最优算法。