题解-leetcode?镜片最小移动次数

虽然已经不用打比赛了,但难得有次机会打了一套题,在最后一个小时不到开了一个题,最后临结束2分钟AC了,真惊险;觉得题还挺有意思的,就记录一下题解,不过题目似乎还没公开。

题目大意

有一种多层材料样品,每个样品都有n层,每层由m个等长块组成,每层保证至少一个块是透明的。现在需要观察这种材料的光学特性,需要把每层的透明块移动到同一垂直位置(不允许悬空或透过空气观察)形成一个通光孔,问最少需要移动多少次。

输入

第一行两个两个整数 n,m
1~n+1行,每行m个整数ai1表示透明,0表示不透明
2 <= n,m <= 1000
ai∈[0, 1]

输出

一行,包含一个整数,表示最少移动次数。

样例数据1

输入:

4 5
0 0 1 0 0
0 0 0 1 0
0 1 0 1 0
0 0 0 1 0

输出:

1

解释:

第一层向右移动一次,即可:

  0 0 1 0 0
0 0 0 1 0
0 1 0 1 0
0 0 0 1 0

样例数据2

输入:

4 5
0 1 0 0 0
1 0 1 0 0
0 0 1 1 0
1 0 0 0 1

输出:

3

解释:

第一层向左移动一次,第三层向左移动两次;或者第一层向右移动一次,第四层向右移动三次:

  0 1 0 0 0
    1 0 1 0 0
0 0 1 1 0
    1 0 0 0 1
或
  0 1 0 0 0
1 0 1 0 0
0 0 1 1 0
    1 0 0 0 1

解题过程

顺带一提,题目最后还专门提醒了暴力穷举能够通过的样例很少。看到这句话就想起来我之前做的一个梗图:

我刚想到了一个O(nn)的算法

另外我这次没用C写,leetcode好心地屏蔽了输入输出代码,直接拿到一个二维数组。鉴于读完题后大概就剩40分钟,光速摸了一个穷举然后TLE了,然后再回来理解题目。

思考穷举的计算过程,由于无论通光孔出现在哪个位置都可以,那么第一层的位置也不是固定的,也可以同时查找左右两个最近的通光孔,最后想办法减去整体移动的次数,但计算规模还是O(nn)
再思考每次都是给每层要找到最近的一个透明片,这个数据实际上是被重复计算的,我们可以提前完成这些计算,当前位置到前、后孔的距离储存下来,如样例1会得到一个新二维数组:

2 1 0 1 2
3 2 1 0 1
1 0 1 0 1
3 2 1 0 1

每层数字的意义变为,将最近的通光孔移动到这个位置需要的操作数,完成这个计算的复杂度是O(n2);列出一组数据之后发现,每列所有数字的和即将这列移动到通光所需要的操作数,而各列和的最小值即题目所求的解,求解复杂度也是O(n2),数据规模1000应该是绰绰有余了。

参考代码

略,估计等题目放出来后再写一遍;15分钟敲正解真是手抖得不行,4个while给每层算距离都敲错,最后2分钟过题真刺激。

后记

所幸是个贪心题,这点时间开个动态规划可能就写不完了。

如果考虑要出个类似的题目,比如把材料改成磁盘,每层都是圆形的,计算距离时可以绕接。如果输入透光率不只0和1,再要找透光率最大的,应该就要上动态规划解了。

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

您正在使用您的 WordPress.com 账号评论。 注销 /  更改 )

Twitter picture

您正在使用您的 Twitter 账号评论。 注销 /  更改 )

Facebook photo

您正在使用您的 Facebook 账号评论。 注销 /  更改 )

Connecting to %s

%d 博主赞过: