今天在写牛客小白赛的时候,遇到一个贪心题。
题意是给五行字符串,'*'代表矿石,‘#’代表石头,第三行为矿道,其余四行均被矿石和石头铺满。我们只能垂直于矿道挖,不能拐弯,求在有限的体力h内,挖到最多的矿石 (挖一次矿石或石头消耗一个体力)。
只要保证优先挖矿石,尽量最后或不挖石头的贪心思路。
思路很正确,但我到比赛结束都没A过去。让我一度怀疑是不是思路的问题或者哪里没有考虑到。
我是这样写的:
我先计算出所有的矿石sum,然后计算能直接挖到的矿石cnt,最后比较体力h和cnt的大小关系,判断是否需要继续挖,如果继续挖,那么每次就需要挖两次才能得到一个矿石。很自然(h-cnt)/2和sum-cnt中取最小值加上cnt即为答案。
赛后思路确实没问题,但犯了一个小小的错误,但思考之后,我想这不简单的是一个小问题。
小问题是在求矿石的总数时,我赛时是这样写得:
先别往下看正解。思考一下,我的写法是否有问题?是哪里有问题?
很明显,只要当前遍历的列有矿石就sum++。这里会对同一列在第1行和第5行的石头,只计算了一次。
正解如下:
在赛时,以及整体的代码量下,真的不仔细观察这个点,还挺难发现的。
赛后发现这个错误后,后悔莫及,但也值得深思。我需要思考赛时在写这段代码的时候是如何思考的。
拿到此题,一看贪心,脑子中已经有大体的思路和代码。然后将思路分解,标准输入输出之后,开始求矿石总数、求可以直接挖到的矿石总数、比较体力值、取最小值等等。在写求矿石总数的时候因为这段代码太简单了,其实脑子里已经开始想着挖可以直接挖到的矿石总数的,已经心不在笔下,也就是这段代码纯纯在靠思维的肌肉记忆来写。
也就是思维惯性。更多地去依靠经验和记忆去执行逻辑,而非思维和头脑,也可以是说再用归纳法思维去解决这个事情,而且还没用好归纳法思维,如果去用思维和头脑做这件事情的话,会很快意识到错解的不合理性(因为演绎法思维是需要一步一步推理的),而归纳法思维凭借经验和记忆,思维是跳跃的,中间省略了很多步骤,忽略了其不合理性。||在数学中也是集合并集的意思,所以误以为是所有情况。
如何解决这个问题呢?
其实很简单,将思维放在笔下,正在写的东西,运用演绎法思维能保证层层逻辑的合理性。将整体的思路写在纸上,防止遗忘细节或某个思路过程。
总之,在学习理工科内容更需要演绎法的思维,保证每层逻辑的合理性,而不是大都凭着经验和想当然。