team2012-D1-sol-0037

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

本题是一道不算蘑菇的格子蘑菇题。注意到骑兵获得的石头和开采获得的石头是相互独立的，所以分开做。二者都有贪心策略： 对于骑兵来说，bfs一下算出到第t个回合结束，最多可以拿到多少石头。而开采方面则是用一个大根堆来维护还未分配工人的土地，每次有一个新的工人可以分配的时候，就放到堆顶的那块土地上去。因为土地的V很小（<= 50），所以可以暴力算出每一个回合可以出产多少石头。然后求一下前缀和就好了。这个部分直接暴力模拟每一个回合，直到回合结束时获得的石头总数达到要求。判断无解有两种办法，一个是估计一下最多可能多少个回合后再也没有石头可以获得，循环的时候把这个作为上限，最后check一下答案是不是等于这个上限；另一个是直接算出最终你可以获得的石头数量，判断一下是否大等于需求C。

本题是一道不算蘑菇的格子蘑菇题。注意到骑兵获得的石头和开采获得的石头是相互独立的，所以分开做。二者都有贪心策略： 对于骑兵来说，bfs一下算出到第t个回合结束，最多可以拿到多少石头。而开采方面则是用一个大根堆来维护还未分配工人的土地，每次有一个新的工人可以分配的时候，就放到堆顶的那块土地上去。因为土地的V很小（<= 50），所以可以暴力算出每一个回合可以出产多少石头。然后求一下前缀和就好了。这个部分直接暴力模拟每一个回合，直到回合结束时获得的石头总数达到要求。判断无解有两种办法，一个是估计一下最多可能多少个回合后再也没有石头可以获得，循环的时候把这个作为上限，最后check一下答案是不是等于这个上限；另一个是直接算出最终你可以获得的石头数量，判断一下是否大等于需求C。