2793_Deep_模拟

发布于 2017-10-26  941 次阅读


---恢复内容开始---

题目描述

失败的燃烧军团想要逃回深渊,Khadgar 想要追击它们。 
然而进入深渊的传送门只有一座,燃烧军团和Khadgar 各有一些法力水晶,由Khadgar 先手,双方每次可以作出如下选择: 
• 使用一个法力水晶,使得传送门的法力等级增加一。 
• 不用法力水晶,让对方增加等于传送门法力等级的深度,然后将传送门的法力值清零。特别地,若法力水晶数不为零且传送门法力等级为零则不能进行这样的操作。 
双方都会采取最优策略使自己的最终深度与对手深度的差最大(初始时深度均为零)。 
现在多次给定双方起始的法力水晶数量A, B,求Khadgar 与燃烧军团的的最终深度差。


 

思路

我们先考虑有一方为0, 那么深度差只可能为a-b

我们考虑后手的最佳策略肯定是让先手只剩一个,然后利用这一个使自己获利,且先手无法选择故为a-b-2


#include 
inline int read()
{
	int x = 0, p = 1; char ch = getchar();
	while (ch < '0' || ch > '9') {if (ch == '-') p = -1; ch = getchar();}
	while (ch >= '0' && ch <= '9') {x = (x << 1) + (x << 3) + ch - '0'; ch = getchar();}
	return x * p;
}
int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
	{
		int a = read(), b = read();
		int ans = 0;
		if (a == 0 || b == 0)
			ans = a - b;
		else ans = a - b - 2;
		printf("%d\n", ans);
	}
}

  

 

]]>