avoidland是一个用n个棋子在n×n板上玩的拼图。棋子最初放置在棋盘的正方形上，每个正方形最多有一个棋子。其目的是移动典当，使它们“避免”对方不能有一行或一列有多个典当。在一次移动中，典当可以移动到相邻的未占用的广场，即与典当的当前位置共享一个边的广场，并且没有典当给定棋子的初始位置，解谜所需的最少移动次数是多少？
输入
第一行包含一个整数n，然后是n行。第i行包含第i个棋子的初始行和列坐标，用空格分隔每个坐标是1到n之间的整数。您可以假设n最多为1000000。
输出
该行包含解决该难题所需的最少移动次数。
Sample Input 1
3
1 3
2 3
3 1
Sample Output 1
1
Sample Input 2
4
1 4
4 1
1 1
4 4
Sample Output 2
4
我的方法：
解决方案要求每行和每列都有一个典当。
对于初始配置，创建一个最右边的列，其中包含每行中典当数量的总和。
做一个最下面的行，包含每列中典当数量的总和。
现在我们需要找到使这些数组中的每一个都成为1的最小步骤数，并将它们相加，但我不知道如何做到这一点。
最佳答案
我认为你的方法很好计算完每一行/列中棋子的直方图后，可以使用贪心算法来计算移动次数。
假设我们有一个0,0,3,1直方图，我们需要把它变成1,1,1,1。
很明显，我们不妨把最靠近左边的棋子移到第一个位置，把最靠近左边的第二个棋子移到第二个位置，等等。
因此，只需遍历直方图，并将找到的第i个棋子与位置i（我们要放置它的位置）之间的距离相加。
例如，在Python中：
A = [0,0,3,1]
t = 0
i = 0
for pos,count in enumerate(A):
for k in range(count):
t += abs(pos-i)
i += 1
print t
这将打印3的答案，对应于向左移动一个棋子两次，向左移动一个棋子一次。
复杂性是O（n），因为内部循环对每个棋子执行一次。