PAT 2-10. 海盗分赃（25）

题目链接：http://www.patest.cn/contests/ds/2-10

解题思路：参考：http://blog.csdn.net/linsheng9731/article/details/22613483?utm_source=tuicool

假设一种普通的情况，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）

整个的过程如下：

（0，10）

（9， 1， 0）

（7， 0， 2，1）

（7 ，0， 1， 0，2）

（6，0，1， 2， 1，0）

（6， 0， 1，2， 0， 0，1）

以上的推理当然都是基于一定的假设前提的，最重要的前提就是海盗足够聪明，会考虑极端情况，只讲理性，所以他们会从后面开始考虑。

其实只要仔细观察上述数列我们就会总结出规律：ans=D-P/2-1;除了情况3之外。,情况3的规律是:ans=D-P/2

代码如下：

#include<iostream>

using namespace std;

int main()

{

	int d,p,ans;

	cin>>d>>p;

	if(p==3)

	{

		ans=d-p/2;

	}

	else

	{

		ans=d-p/2-1;

	}

	cout<<ans<<endl;

	return 0;

}

巴特西

PAT 2-10. 海盗分赃（25）

最新文章

热门文章