时间戳

首页 > 解决方案 > 如何处理基于排序的算法/理解代码背后的直觉？

algorithm - 如何处理基于排序的算法/理解代码背后的直觉？

问题描述

我一直被困在一个算法问题上，我需要帮助才能取得进展。问题陈述如下。

问题定义：

2N公司计划面试一些人。把i-th人飞到城市的成本A是，把人飞到城市costs[i][0]的成本是。i-thBcosts[i][1]

返回将每个人飞往一个城市的最低成本，以使N人们准确地到达每个城市。

输入：[[10,20],[30,200],[400,50],[30,20]]

输出：110

我见过一些解决方案，它们涉及排序。

但是，我无法获得直觉。

有人可以向我解释如何解决这个问题吗？

这是我找到的示例解决方案：

    public int twoCitySchedCost(int[][] costs) {
        Comparator<int[]> comparator = (a, b) -> Math.abs(b[0] - b[1]) - Math.abs(a[0] - a[1]);
        Arrays.sort(costs, comparator);
        int N = costs.length / 2,
                c1 = 0,// counter for the station A
                c2 = 0,// counter for the station B
                ans = 0,
                i = 0;
        while (i < 2 * N) {
            if ((costs[i][0] <= costs[i][1] && c1 < N) || c2 == N) {
                ans += costs[i++][0];
                c1++;
            } else {
                ans += costs[i++][1];
                c2++;
            }
        }
        return ans;
    }

标签： algorithmsorting

解决方案

让我们先来看看这个算法在做什么。它根据每个人去城市 A 和城市 B 的成本之间的差异对每个人进行排序。例如，如果人 X 去城市 A 和 B 的成本分别为 1 和 100，而人 Y 的成本分别为 49 和 50分别去城市 A 和 B，那么人 X 在排序顺序中会比人 Y 来得更早。我会尝试在比较器中插入一些示例来实现这一点。

接下来，算法贪婪地（意味着不需要对后来的人有远见）按照排序列表的顺序给每个人他们更便宜的城市。这种情况一直持续到一个城市“满员”，即有 N 个人分配给它，此时其他所有人都被分配到另一个城市。这发生在 while 循环和两个条件语句中。你能看出这个逻辑是如何发挥作用的吗？

最后，它引出了为什么这个解决方案有效的问题。请注意，如果我们取消了每个城市必须有 N 个人去的约束，那么最好的解决方案当然是将每个人送到他们更便宜的城市。但是，鉴于此限制，这并不总是可行的。每次有人不访问他们的最低成本城市时，他们都会偏离让每个人都去他们更便宜的城市的最低解决方案。也就是说，它们的偏差正好是城市 A 和城市 B 之间成本差异的绝对值。因此，我们考虑让那些成本差异很大的人成为他们的第一选择是有道理的（否则，如果他们有偏离，成本的变化对他们来说是最大的）。结果，这就是为什么我们贪婪地按这种排序顺序考虑人。

推荐阅读