虽然已经不用打比赛了，但难得有次机会打了一套题，在最后一个小时不到开了一个题，最后临结束2分钟AC了，真惊险；觉得题还挺有意思的，就记录一下题解，不过题目似乎还没公开。
题目大意
有一种多层材料样品，每个样品都有n层，每层由m个等长块组成，每层保证至少一个块是透明的。现在需要观察这种材料的光学特性，需要把每层的透明块移动到同一垂直位置（不允许悬空或透过空气观察）形成一个通光孔，问最少需要移动多少次。
输入
第一行两个两个整数 n,m
第1~n+1行，每行m个整数ai，1表示透明，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，再要找透光率最大的，应该就要上动态规划解了。
兰科印象 