M*******a
发帖数: 1633 | 1 就是一维直线上面有N个洞和M个老鼠，洞和老鼠的坐标都知道，一个洞最多只能容纳一
个老鼠，N>=M。每个老鼠移动速度都一样，现在要求怎样再最短时间内让所有老鼠都入
洞。 |
b********r
发帖数: 620 | 2 马中还是苹果还是空气？DP from holes ?
【在 M*******a 的大作中提到】
: 就是一维直线上面有N个洞和M个老鼠，洞和老鼠的坐标都知道，一个洞最多只能容纳一
: 个老鼠，N>=M。每个老鼠移动速度都一样，现在要求怎样再最短时间内让所有老鼠都入
: 洞。
|
l*********b
发帖数: 65 | 3 想问一下 是不是比如老鼠面前的洞已经被别的老鼠占了 那么这只老鼠就要踏过同伴是
身体去找下一个洞？。。老鼠是能选择左或者右移动么 |
s**********k
发帖数: 88 | 4 假设洞和老鼠各自按坐标拍好了序，
第M个老鼠应选(第M个洞,...,第N个洞)
中离自己最近的,假设它选的是第K个洞，第M-1个老鼠应选(第M-1个洞,...,第K-1个洞)中
离自己最近的。如此类推。
【在 M*******a 的大作中提到】
: 就是一维直线上面有N个洞和M个老鼠，洞和老鼠的坐标都知道，一个洞最多只能容纳一
: 个老鼠，N>=M。每个老鼠移动速度都一样，现在要求怎样再最短时间内让所有老鼠都入
: 洞。
|
M*******a
发帖数: 1633 | 5 最优解里面应该不存在这种情况。
【在 l*********b 的大作中提到】
: 想问一下 是不是比如老鼠面前的洞已经被别的老鼠占了 那么这只老鼠就要踏过同伴是
: 身体去找下一个洞？。。老鼠是能选择左或者右移动么
|
p***y
发帖数: 637 | 6 4个洞，3只老鼠都在0号洞左边？
鼠鼠鼠洞洞洞洞
【在 M*******a 的大作中提到】
: 最优解里面应该不存在这种情况。
|
s*********1
发帖数: 16 | 7 非牛说说自己的看法。
这道题应该是一个很典型的动态规划应用题。
因为老鼠和洞都在一维直线上，
不妨把问题极简化为：
老鼠是N个不同的整数，取值范围是0到正无穷（把直线处理成射线，或者0到某个定值
，处理成线段）
洞也是M个不同的整数，取值也是0到正无穷。
现在就是，从M个数种取N个值，跟N个老鼠的数一一匹配，然后把匹配以后每对数（一
个老鼠一个洞）的差的绝对值相加，求最小值。
那么我们以N个老鼠，每只老鼠为一轮loop做动态规划。
假设第一只老鼠坐标2，那么他找到坐标为3的洞为最小距离。
好，我们认定第一轮结果，然后，我们把第二只老鼠再带进来，假设第二只老鼠坐标为
5，而他找到最近的洞为坐标6.那么这次结果没有冲突，进入下一轮。但是，如果第二
只老鼠坐标为3，那么冲突产生。所以要重排。
以此类推产生动态规划。
这是个最简单的线性动态规划了吧？
这题还有个捷径，就是最左端坐标的老鼠找的洞不会影响最右端老鼠找的洞（因为距离
最远），所以可以从两端向中间进行动态规划。
好好把动态规划看看，然后有队列和散列表有基本知识，就能做出这道题了。 |
e***m
发帖数: 92 | 8 “然后把匹配以后每对数（一 个老鼠一个洞）的差的绝对值相加，求最小值“
--------难道不是最小化差的绝对值的最大数吗？
【在 s*********1 的大作中提到】
: 非牛说说自己的看法。
: 这道题应该是一个很典型的动态规划应用题。
: 因为老鼠和洞都在一维直线上，
: 不妨把问题极简化为：
: 老鼠是N个不同的整数，取值范围是0到正无穷（把直线处理成射线，或者0到某个定值
: ，处理成线段）
: 洞也是M个不同的整数，取值也是0到正无穷。
: 现在就是，从M个数种取N个值，跟N个老鼠的数一一匹配，然后把匹配以后每对数（一
: 个老鼠一个洞）的差的绝对值相加，求最小值。
: 那么我们以N个老鼠，每只老鼠为一轮loop做动态规划。
|
i*********n
发帖数: 58 | 9 把老鼠和洞一起排序，从左往右，遇到老鼠，就填进左边或右边邻近的洞，取小值。如
果左或者右边洞已经填满，要往左右继续找到空的洞，然后取小的值。此题应该是一维
DP问题。 |
c*****w
发帖数: 50 | 10 May also use binary search. Given a time t, use max flow/min cut/matching to
know whether t is feasible
[发表自未名空间手机版 - m.mitbbs.com] |
l******a
发帖数: 14 | 11 This is a max/ min flow problem from mouse to hole(bipartite graph) |
l******a
发帖数: 14 | 12 Sort the mouse for left to right.
Add mouse one at a time, keep a current time length that all included mouses
can run to holes. And keep the current mapping.
When adding new mouse, if min time hole for that mouse is not mapped, added,
move on.
If no empty hole on left for existing included mouses, pick the min hole
from not mapped hole, added and move on.
If min hole is occupied, and there are empty holes on the left, pick the
closest empty hole, check if the max time if move all existing mouse to
their left hole(only for mouses on right side of the empty hole), and the
min time if the current mouse pick a non occupied hole. Pick the smaller
time cost, add, rearrange accordingly. |
