土匪也疯狂

题目描述

有5个贪婪的土匪抢劫到100个金元宝，在分赃的时候犯起了难，这个时候土匪头子说根据年龄的大小，年纪较大的土匪先讲分赃方案，如果超过50%的人不同意就将这个出方案的土匪活埋，然后换下一个年纪较大的土匪出分赃方案，依次类推。这5个土匪都比较爱惜自己的生命，并且都特别聪明且理智，但他们不爱惜同伴的生命，就算是平均分配他们都不会同意。如果你是年纪最大的那个土匪，你会怎样分配既能保住命又能获得尽可能多的金元宝？

思路解析

看到这里，不少同学已经一脸懵了，估计题目都没读懂。不要慌，动动您发财的小手先点个赞关注一下不迷路，首页还有很多熬夜精心写的题解。下面我们来一步步分析下这个问题。

1. 如果土匪只有一个，我们亲切的称他为匪1，那毫无疑问所有的金元宝都是他的。
2. 如果又有一个年龄更大的匪2加入，那匪2会先出方案，匪2会把所有的金元宝都分给自己，即使匪1反对，总的反对票也不会超过50%。这个时候分配情况如下图。

3. 如果又有一个年龄更大的匪3加入，那匪3会先出方案，匪3会给匪1一个金元宝，匪1会欣然接受，因为如果他把匪3投死，匪2一个金元宝都不会给他。这个时候分配情况如下图，总的反对票不会超过50%。

4. 如果又有一个年龄更大的匪4加入，那匪4会先出方案，匪4会给匪2一个金元宝，匪2会欣然接受，因为如果他把匪4投死，匪3一个金元宝都不会给他。这个时候分配情况如下图，总的反对票不会超过50%。

5. 如果又有一个年龄更大的匪5加入，那匪5会先出方案，匪5会给匪1和匪3各一个金元宝，并且他们会欣然接受，因为如果把匪5投死，匪4一个金元宝都不会给他们。这个时候分配情况如下图，总的反对票不会超过50%。

所以作为年龄最大的土匪只需要给年龄最小的土匪和年龄第三小的土匪各一个金元宝，他就既可以保住生命，又能拿到98个金元宝。

看到这里是不是豁然开朗，值不值得您一个赞，这种自下而上的推导方式有没有很熟悉，和动态规划一毛一样。

现在就业竞争比较激烈，僧多粥少，很多大企业在面试的时候直接用这种思维题来筛人，虽然不合理，但也无可奈何，所以养成一个良好的思维习惯也是非常重要的。

思考：聪明的你能否推导出有n个土匪，年龄最大的土匪要如何分配才能既保住命又能获得尽可能多的金元宝？

最后分享一份力扣题目列表，这里既提供了经典题目列表，还提供了对应的高质量题解，让刷题更有效率。非常适合刚刚开始刷题或者为了找工作刷题的同学。

此题目列表包含的知识点是比较全面的。

常用的数据结构： 数组、字符串、链表、二叉树、图、前缀树、集合、映射、栈、队列、堆都有覆盖。

常用的解题方法： 递归、迭代、二分法、回溯、贪心、动态规划、位运算、双指针、模拟、拓扑排序、桶排序、单调栈、深度优先搜索、广度优先搜索都有覆盖。

  在线文档  

另外题目列表和题解都开源在github上了，欢迎大家提建议。

---

关注@溜达虎爱编程，学习算法不辛苦！