我看到你在思否上的提问了,别人回答得很好了,把我想说的甚至我想吐槽的基本都写到了(就是这个毫无卵用的n和明明是下山偏偏叫爬山的问题),但是他是假设p中没有重复的数字,也就是没有考虑顶不为点而是一条线的情况,我就补充一下吧。
对于一组形如[7 5 6 8 9 4 5 7 7 7 6 3 3 3 8]的数据,我们可以把每一个使数据排列从【降序、相等、升序】中发生变化的转折点称为顶,在该数据中为[7 5 6],7和5,[8 9 4]的4,[5 7 7]中的第一个7,[7 7 6]中第二个7,[6 3 3]中的第一个3,[3 3 8]中的第二个3和8。这些数字都是数据的顶,而顶之间的数字我们可以称之为坡。首先,根据游戏规则,如果先手落在一个坡数上(即一组有序数据的非两端处),那么只要后手落在这个坡数的降序一侧第一个数(可能是顶也可能是坡),那么先手下一步就没有移动空间了(因为要求∣x′−x∣=1说明只能左右移动一个数,x′≠y说明不能移动到降序侧的y,所以,只能移动到升序侧,则px'>px,与规则不符),所以可以知道,两人在最优策略下,先手下在坡上必输。
现在考虑顶。这里我们引入坡长这个概念,一个顶的一侧坡的坡长为该坡中比顶小的数字的个数,或者是比顶大的数字个数的相反数。举两个例子,对[7 5 6]中的顶7,左坡长为0,右坡长为1。对于[7 5 6 8 9 4]中的顶5而言,左坡长为-1,右坡长-3。因为移动要满足px′<px的条件,对于坡长为0或负数的顶而言,不能从该顶向这个坡移动。对于两个坡长都为非正数的顶,下在该顶处将直接无法移动。而对于一边坡长为正,一边坡长非负数的顶而言,非负数一侧无法移动,所以下在该顶处和上面分析的下在一个坡点处完全相同。所以我们得到结论,想要赢,必须至少下在一个两坡长都为正数的顶处。
对于坡长不相等的顶来说,假设该顶的左坡长为m,右坡长为n,(这里假设m<n,n<m的结论完全一样,是对称关系),如果当先手下在该顶处,后手直接落在右坡第一个位置。我们可以注意到,此时坡长即为可以移动的轮次,因为m<=n-1,所以先手一定会先不能移动,相等时由于处于先手,也是先卡死在坡底导致输掉。而对于坡长相等的顶来说(m=n),必有m>n-1,当先手移动m次后,后手会无法移动输掉比赛。所以我们得到结论,想要赢,必须至少下在一个两坡长都为相等正数的顶处。
考虑先手下在左右坡长为n的顶上,如果此时有任意一个顶的任意一侧坡长为m>=n,只要后手下在这个顶上,后手的移动次数就不少于先手,当先手用完次数就会先无法移动从而输掉游戏。所以我们得出最终结论,先手要赢,只能下在两坡长都为相等正数且该数必须为左右坡长的唯一最大值的顶处。
所以有以下python代码
n = int(input('请输入一个整数:'))
num = input('请输入%d个整数,以空格隔开:' % int(n)).split(' ')
p = list(map(int, num))
# 这个数组用来储存小山顶的左坡长
leftLenList = []
# 这个数组用来储存小山顶的右坡长
rightLenList = []
# 由于python没有直接的枚举类型,这里就用字典变量来代替
State = {
'RISE': -1,
'ZERO': 0,
'FALL': 1,
}
def climb():
# 可以认为数组左端点的处在坡长为0的坡上
lastState = currentState = State['ZERO']
LenCount = 1
for i in range(len(p) - 1):
currentState = State['RISE'] if p[i] < p[i + 1] else (
State['ZERO'] if p[i] == p[i + 1] else State['FALL'])
if currentState != lastState:
leftLen = 0 if lastState == State['ZERO'] else (
LenCount if lastState == State['RISE'] else -LenCount)
rightLen = 0 if lastState == State['ZERO'] else (
-LenCount if lastState == State['RISE'] else LenCount)
leftLenList.append(leftLen)
rightLenList.append(rightLen)
LenCount = 1
lastState = currentState
else:
LenCount += 1
rightLenList.pop(0)
# 处理数组右端点
currentState = State['ZERO']
if currentState != lastState:
leftLen = LenCount if lastState == State['RISE'] else -LenCount
rightLen = -LenCount if lastState == State['RISE'] else LenCount
leftLenList.append(leftLen)
rightLenList.append(rightLen)
rightLenList.append(0)
# 出于性能考虑,就不调用max,inidex和count函数了,而是自己写循环
maxLen = 0
maxIndex = []
for i in range(len(leftLenList)):
if leftLenList[i] >= rightLenList[i]:
bigger = leftLenList[i]
else:
bigger = rightLenList[i]
if bigger > maxLen:
maxLen = bigger
maxIndex = [i]
elif bigger == maxLen:
maxIndex.append(i)
return 1 if len(maxIndex) == 1 and leftLen[maxIndex[0]] == rightLen[maxIndex[0]] else 0
print(climb())