详解：海盗分赃（25 分）海盗分赃（25 分）

62 阅读 0 评论 41 点赞

我是靠谱客的博主潇洒羊，最近开发中收集的这篇文章主要介绍详解：海盗分赃（25 分）海盗分赃（25 分），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

海盗分赃（25 分）

P 个海盗偷了 D 颗钻石后来到公海分赃，一致同意如下分赃策略：

首先，P 个海盗通过抽签决定 1 - P 的序号。然后由第 1 号海盗提出一个分配方案（方案应给出每个海盗分得的具体数量），如果能够得到包括 1 号在内的绝对多数（即大于半数）同意，则按照该分配方案执行，否则 1 号将被投入大海喂鲨鱼；而后依次类似地由第 2 号、第 3 号等等海盗提出方案，直到能够获得绝对多数同意的方案出现为止，或者只剩下最后一位海盗，其独占所有钻石。请编写一个程序，给出第 1 号海盗的钻石分配方案中自己分得的钻石数量。

附带的三个假定：

“聪明”与“贪婪”假定：每个海盗总能够以本人利益最大化作为行为准则；
“人性化”假定：在能够取得尽量多钻石的情况下，海盗不会故意致同伙于死地；
“无偏见”假定：海盗之间没有个人恩怨，分给其他海盗钻石的次序以小序号优先为原则。

输入格式：

输入在一行中给出 2 个正整数 D 和 P（3≤P≤D≤100）。

输出格式：

输出第 1 号海盗的钻石分配方案中自己分得的钻石数量。

输入样例：

10 7

输出样例：

题目解析：读懂了题目就很简单了，海盗分赃问题就是要用倒推法来找规律，找到了规律，代码就是几行的事儿。

以样例为例：

10个钻石，当两个人分时，要获得两个海盗的同意，1号海盗的方案只能是（0，10），要不然2号因为“贪婪”会投死1号

当三个人分时,方案是(9,1,0),此时的2号为上面的1号,虽然只给他一颗,但他还是会同意,要是反对的话,到了下轮就一颗也没有了,两人同意,方案通过

当四个人分时，方案是(7,0,2,1),此时的4号是上面的3号，3号是上面的2号，依次类推，此时3，4得到的宝石比三人份时要多，所以同意，四人同意，方案通过

依次类推

当五人分时方案为（7，0，1，0，2）六人是（6，0，1，2，1，0，）七人是（6，0，1，2，0，0，1）

清晰一点就是这样：

1号2号3号4号5号6号7号

0，10 如果只剩两个人分就是这样，6号海盗为了活命会将所有钻石分给7号

9， 1， 0 如过是三个人分，6若是反对，到了2人轮，他就一刻也分不到，所以赞成

7，0，2，1 四个人分，6号若反对，到了3人轮分的还要少，7若反对，下轮1颗也没有

7，0，1，0，2 依次类推，只要分到的钻石比再少1人分到的要多，就会赞成

6，0，1，2，1，0

6，0，1，2，0，0，1

然后就很容易找到规律了，当人数大于三时，ans = d-p/2-1，三个海盗分的时候，只要给另一个海盗1颗就行了，特判一下就是ans = d-1 ;

#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std;
int main()
{
int p , d ;
cin>>d>>p;
int ans ;
if(p==3)
ans = d-1 ;
else
ans = d-p/2-1;
cout<<ans;
return 0;
}