-3

我正在尝试解决停止邮递员问题,但我找不到任何算法来解决它。问题是这样的:

有 n 个房子,编号从 1 到 n,还有 n 个邮递员,每个房子都有 n 封信要寄到每个房子里。邮递员决定了一个计划,即每个邮递员在不同的时间准确地访问每个房子一次,即任何房子在任何时候最多有一个邮递员。由于没有任何邮递员像其他任何邮递员一样,因此邮递员希望在将邮件投递到 n 个房子的过程中,没有邮递员会遇到任何其他邮递员。因此,他希望邮递员在特定房屋之后停止邮寄。也就是说,邮递员想要找到一个序列,这样第i 位邮递员一旦访问了那个房子,就会在第 stop[i] 个房子之后停止发帖。由于他想确保每个房子最多有一个职位,他必须选择序列停止这样,如果邮递员 A 在时间 T 访问房子 H,并且他在房子之后停止投递,那么在时间 T 之后没有其他邮递员访问房子 H。帮助邮递员找到这样的序列stop

输入如下:

首先n(1≤n≤100 ,表示邮递员和房屋的数量。然后是n行,每行包含n 个正整数。第i行中的第 j 个整数表示第i 个邮递员访问第j 个房子的时间。

示例:n = 3

顺序是:

1 2 3

4 5 6

7 8 9

输出的停止数组应该是:

3 2 1,即第 1 邮递员在第 3 宫、第 2 在第 2 宫和第 3 在第 1 宫停止投递。

我应该使用什么算法来解决这个问题?

4

2 回答 2

0

更新,我的最后一个答案是错误的。

新解决方案:在每一步中找到每行中的最小值,然后取其中的最大值,这将是第 i 个邮递员的停止点。在接下来的每一步中,不再考虑那个邮递员

对于您提供的样本:

1 2 3 
4 5 6 
7 8 9

第一步,我们找到 1 4 7,其中最大为 7,所以第三个邮递员停在 1st house(stop[3] = 1) 之后我们不考虑第一列和第三行 第二步我们找到 2 和 5 , 最大值为 5 所以 - stop[2] = 2; 第三步停止[1] = 3;

那么,为什么这是真的,如果我们在某个步骤中选择了正确的数字,我们知道对于同一列中的任何数字,它要么小于我们的数字(这意味着它以后不会引起问题)要么大于我们的数字,但是该行的数字小于它稍后将被选中,这样我们列中的较大数字就不会被使用

对于@Wayne Rooney 提供的示例

1 4 2
8 6 9
5 7 3

第一步 找到 1, 6, 3, 选择 6 第二步 找到 1, 3 选择 3 第三步 1 答案:1, 2, 3

于 2012-08-09T09:58:08.157 回答
0

@Herokiller 你的算法不正确。例如:

1 4 2

8 6 9

5 7 3

您的输出将是:

Step1:取元组 (8,7,3) min 其中 7 然后取 (8,9) 所以 min 是 8 最后 (2) 所以输出是 3,1,2

但答案将是 1 2 3 即(1,6,3)

即使我不知道这个问题的答案,但我有一个矛盾的测试用例,我无法评论你的消息,因为它被标记为正确答案

于 2012-08-10T21:26:10.490 回答