——以及贪心算法真的能陪你走好远
今天 Google 的 Hash Code 在线比赛结果放榜了。很遗憾，我们的队因为到比赛即将结束时才第一次提交答案，没能在截止之前发现一个很小的 bug。因此也不能免费去法国玩儿了。不过就一次增进友谊的机会，或者一晚上的谈笑风生的材料而言，已经很不错了。
题目很长很 daunting：在规定的时间内，要安排一批无人机（天哪我连这个单词都不认识，退赛吧）去一些仓库里取货，然后给不同坐标的客户送货。每送完一单，获得的分数和此时剩余的时间成正比。这里面可优化的细节特别多，但其中「取同类商品可以省几个时间单位」这种就不能当来重点。看看给定的输入也是有用的，比如大部分单都挺大，用一架机送多个单的实用性不强。
我们的算法演示，绿点代表已经送完的订单
我一开始就注意到，所有单的得分能力都是平等的，所以应该优先送那些容易完成的。如果需要跑多趟，尽量相差不远，因为只有单上所有物件都到了才能算分。基于这一点，我写了一个优先级计算函数，每次从中找出下一个要处理的单。处理该单，并更新各仓库存货和各单优先级。
之后，我的队友们设计了送单的算法。我们有一个分歧，就是要选择与目的地最近的仓库，还是选择存货能最大限度地覆盖这张单的仓库。最后我们选择了后者，并准备优化它，比如覆盖量达到无人机载重的九成，就取其中最近的仓库。选完仓库，再以仓库为中心，找最近的可用的无人机来送。我后来改进为也考虑采用那些目前被占用的无人机，如果它们很快变得可用，而且位置更近。即，选择在最短时间内能到达该仓库的。
在短短三个多小时里，要用全部四个指令恐怕不易。我们果断只选用了最简单的送货方法：一台无人机负责一张单，去一个仓库取货，去一个地方送货。事实证明这是正确的。如果我们没有写错释放无人机的时间（写错后无人机再也得不到释放，都成了一次性的，成绩可想而知），这个简易的算法可以获得 26 万多分。如果允许负载不满时为下面的单提前带货（前提是这样比从那一单的最优仓库出货还近），可以和第一名一样都是 28 万多分。而代码量只是 114 行而已。
平心而论，第一次参加这样的比赛，能写出能跑的程序我们已经欢天喜地了。毕竟这看起来像是个几百万的大工程啊，回家都可以干快递或出租车了，Google 居然想用免费劳动力来解决（误）？So... 让我们来鉴赏一下那些牛逼闪闪（以及不闪）的队，都叫什么名字吧（按名次排序）——
15 Warsaw Doges (Poland)
20 The Coding Dead (France)
50 Singles In Your Area (Switzerland)
弹窗小广告？
119 The Joy Of Programming ༼ つ ◕_◕ ༽つ (Germany)
颜文字不错，拿走了。
141 YouTube to MP3 Converter (Germany)
147 HashCat (United Kingdom)
164 THE TEAMS LISTED ABOVE HAVE BEEN DISQUALIFIED. (Poland, United Kingdom)
以上企业均已破产。
304 2B||!2B (Lithuania)
莎士比亚也挡不住中文缩略词上脑。
387 Coffee Oriented Programming (Turkey)
有咖啡便是娘。
464 支持Unicode的 (Romania)
这是中国人还是谷歌翻译？
497 SleepyAlgorithms (Italy)
睡法，跟醉拳一样么？
529 reverse (╯‵□′)╯ hashtable ︵┻━┻ (Switzerland)
掀起你的哈希婊！
641 Unsigned Long Long (Netherlands)
这队好像跟我们同病相怜，排名落后，但时间截止后迅速排到前面，可能也是什么 bug 作祟。
656 HashCollision (Belgium)
是说如果大家都叫这名字就会出现队名 collision 么？
1031 Taoist (France)
什么，道士只拿了 0 分？二进制、计算机不是道教么？！
网友评论