首页 > 代码库 > 【博弈】海盗分赃

【博弈】海盗分赃

题目大意:有N(N<=1000)个贪婪的海盗,他们得到了100,000个金币,决定分赃。他们都很精明,都想自己利益最大化,并采取如下策略: 1、 首先N人排好次序。 2、 由编号最大者给出分赃方案。 3、 所有人表决,50%及以上的人赞成就分赃成功,否则转4。 4、 杀掉提案者(总人数少了1),转2。 你的任务:判断第几号海盗得最多金币,有多少个。

 

题解:此题需要绕一个小弯,首先,获得钱最多的一定是第一个人。其次,他只需给所有奇数号的人一枚金币。可以YY一下,奇数永远都受偶数的限制,他们非常可能什么都得不到,所以他们只要有就满足了。所以答案为100000-(n-1)/2。 so easy!