学术板块发的帖子

002发起

002发起----

9997注销

9997注销

11

222112224444

444

4444

103101

103101103101

11

11122

9999待注销

1111

2222

2222

9998注销

111

xxx

小 Y 和小 S 在同一家书店工作，今天他们需要将新进货的书放到书架上。书店的书架平行排成若干排，书架的位置可以看作平面直角坐标系中的整点。第 rrr 排书架包含横坐标为 rrr，纵坐标 ≥0\ge0≥0 的点，出入口为 (r,0)(r,0)(r,0)。 他们每一秒可以走到坐标系中一个相邻的整点。在同一排书架中可以自由走动，但在不同排书架间移动时，由于会被书架挡住，只能从出入口离开后从书架外侧绕行。 形式化地，他们每秒可以从 (r,c)(r,c)(r,c) 走到 (r,c±1)(r,c\pm1)(r,c±1)，或者从 (r,0)(r,0)(r,0) 走到 (r±1,0)(r\pm1,0)(r±1,0)，但若 c≥1c\ge1c≥1，则不能从 (r,c)(r,c)(r,c) 走到 (r±1,c)(r\pm1,c)(r±1,c)。 现在有 nnn 本新书，第 iii 本要放到 (ri,ci)(r_i,c_i)(ri ,ci )。他们要从 (0,0)(0,0)(0,0) 处的书库出发，把所有新书放到对应的书架上。他们可以带着任意多本书移动，到达书架 (r,c)(r,c)(r,c) 时可以立刻把所有要放到 (r,c)(r,c)(r,c) 的书放上书架，往书架上放书的时间可以忽略不计。 现在他们要把书分成两部分，每人负责其中一部分，最后返回出发点 (0,0)(0,0)(0,0)。他们想要知道，怎样适当分配两人负责的书，可以使得用时较长者的用时最短。