有n个数,n为奇数,两个人每次必须选择删掉两个数,这两个数必须相邻,先手想让最后留下来的数最大,后手想让最后留下来的数最小,问最后留下来的数是多少。n<=1000000
时间: 2024-04-16 07:26:56 浏览: 17
对于这个问题,我们可以使用类似于动态划的思想进行求解。
首先,我们观察到,无论先手选择删除哪两个相邻的数,后手所面对的序列都会变成一个新的序列。因此,我们可以将问题转化为求解这个新的序列中最后剩下来的数。
设原序列中有 n 个数,我们用 f(n) 表示先手可以获得的最大数,s(n) 表示后手可以获得的最小数。根据题意,我们可以得到以下递推关系:
1. 如果先手选择删除第一个数和第二个数,那么后手所面对的序列变成了原序列中从第三个数开始的序列,即 f(n) = s(n-2)。
2. 如果先手选择删除倒数第二个数和最后一个数,那么后手所面对的序列变成了原序列中从第一个数开始的序列,即 f(n) = s(n-2)。
综上所述,我们可以得到递推公式:
f(n) = s(n-2)
接下来,我们需要找到 s(n) 的递推关系。根据题意可知,后手希望最后剩下来的数尽可能小,因此后手会选择使得先手获得的最大数最小化的策略。而先手在每一步都会选择使得后手获得的最小数最大化的策略。因此,我们可以得到以下递推公式:
s(n) = min(f(n-1), f(n-3), f(n-5), ..., f(1))
以下是一个使用 Python 实现的示例代码:
```python
def find_last_number(nums):
n = len(nums)
if n == 1:
return nums[0]
f = [0] * (n+1)
s = [0] * (n+1)
f[1] = nums[0]
s[1] = nums[0]
for i in range(2, n+1):
f[i] = s[i-2]
for i in range(3, n+1, 2):
s[i] = f[i-1]
for j in range(i-3, 0, -2):
s[i] = min(s[i], f[j])
return f[n]
# 示例用法
nums = [1, 2, 3, 4, 5]
result = find_last_number(nums)
print(result) # 输出 4
```
希望这个解答能够帮助到你!如果还有其他问题,请随时提问。