题意

P个海盗偷了D颗钻石后分赃($3 \leq P, D\leq 100$),采用分赃策略:

从1号开始,提出一个分配金币的方案,如果能够得到包括1号在内的绝对多数(即大于半数)同意,则执行该方案,否则1号将被投入大海喂鲨鱼;而后依次类似地由第2号、第3号等等海盗提方案。

且有假设:1.绝顶聪明,总以个人利益最大化作为行为准则;2. 在能够取得尽量多钻石的情况下,海盗不会故意致同伙于死地;

分析

倒着分析,

假设一种普通的情况,10颗钻石7个人分。

如果只剩2个人,那么无论2说什么1都会反对,除非他把钻石全给他。也就是下面这种情况。

(0,10)

如果只剩3个人,3知道了如果自己死了2的处境,如果想让自己的提议实现只要争取1个人的同意就好了。所以3会给2号一颗钻石2就会同意3的提议,不然就一枚都拿不到了。这样就变成了:

(9,1,0)

如果只剩4个人,4知道了如果自己死了3的方案,如果想让自己的提议实现只要争取2个人的同意就好了。所以4会给2号多一颗钻石,给1号一颗钻石,1和2就会同意4的提议。这样就变成了:

(7,0,2,1)

如果只剩5个人,5知道了如果自己死了4的方案,如果想让自己的提议实现只要争取2个人的同意就好了。所以5会给3号一颗钻石,给1号2颗钻石。这样就变成了:

(7,0,1,0,2)

如果只剩6个人,6知道了如果自己死了5的方案,如果想让自己的提议实现只要争取3个人的同意就好了。所以6会给4,2号一颗钻石,给3号2颗钻石。这样就变成了:

(6,0,1,2,1,0)

现在我们可以推出7个人的情况了,7知道了如果自己死了6的方案,如果想让自己的提议实现只要争取3个人的同意就好了。所以7会给4,2号一颗钻石,给3号2颗钻石。这样就变成了:

(6,0,1,2,0,0,1)

总结一下就是,有$i$ 个人时,由于知道 $i-1$ 个人时的情况,所以在前一轮选最小的 $i/2$ 个并每个多给一个。

具体的规律是 $P > 3$ 时,总有 $i/2-1$ 个1和一个2;$p=3$ 时为 $(D-1 \ \ 1 \ 0)$.

代码实现应该很简单吧.略

参考链接:http://www.voidcn.com/article/p-cxovyfju-qm.html

05-11 17:42