回答此问题可获得 20 贡献值,回答如果被采纳可获得 50 分。
<p>编辑:<em>新代码</em>。这两种解决方案都非常有效,但由于某种原因并没有改善我的时间效果,这对我来说还没有意义</p>
<p>看到我的绝望,一位朋友向我推荐了他的解决方案,该方案在给定的时间内运行良好,但不知何故在这一特定输入上失败了:</p>
<pre><code>9
1 2 2 3 3 4 4 5
3 6 6 7 3 8 8 9 9 10
</code></pre>
<p>它给出的是“9”而不是“5”。你知道为什么会这样吗</p>
<pre><code>maxNum = int(0)
idxArr = []
def ReadInput():
global array
global firstNum
arr = input().split()
firstNum = int(arr[0])
while int(arr[0]) * 2 + 1 > len(arr):
tempArray = input().split()
arr = arr + tempArray
iterator = int(0)
array = [0] * int(arr[0])
for i in range(1, int(arr[0]) * 2, 2):
tempArray = [0] * 3
tempArray[0] = int(arr[i])
tempArray[1] = int(arr[i + 1])
tempArray[2] = None
array[iterator] = tempArray
iterator+=1
def SortArray(array):
array.sort(key=lambda x: x[1])
array.sort(key=lambda x: x[0])
def MergeDominos(array):
tempNum = int(0)
for item in array:
if (item[2] == None):
iterator = tempNum
counter = int(0)
tempBool = False
try:
while item == array[iterator]:
if (tempBool):
array.pop(iterator)
counter += 1
else:
iterator += 1
counter += 1
tempBool = True
except IndexError:
True == True
if (counter % 2 == 1):
item[2] = counter
tempNum += 1
else:
tempItem = item.copy()
array.insert(tempNum + 1, tempItem)
array[tempNum + 1][2] = int(1)
item[2] = counter - 1
tempNum += 1
else:
tempNum += 1
def GetLengthOfArray(array):
counter = int(0)
for item in array:
counter += item[2]
return counter
def SwitchPlaces(item):
item[0], item[1] = item[1], item[0]
def GetMaxLength(array, tempArray, left, right):
global maxNum
# print("This is temp: ", tempArray)
for i in range(len(array)):
# print("Testing: ", array[i], "Iteration: ", i)
# print("IdxArr: ", idxArr)
if (len(array) <= len(idxArr)):
#print("BREAKING HERE BREAKING HERE BREAKING HERE BREAKING HERE BREAKING HERE BREAKING HERE BREAKING HERE BREAKING HERE BREAKING HERE BREAKING HERE BREAKING HERE BREAKING HERE BREAKING HERE BREAKING HERE BREAKING HERE ")
break
if (i not in idxArr):
#print("Condition:")
if (left == array[i][0]):
#print("LL")
if (i in idxArr):
break
else:
idxArr.append(i)
SwitchPlaces(array[i])
if (len(array) >= len(idxArr)):
tempArray.insert(0, array[i])
if (GetLengthOfArray(tempArray) > maxNum):
maxNum = GetLengthOfArray(tempArray)
if (len(array) >= len(idxArr)):
GetMaxLength(array, tempArray, tempArray[0][0], tempArray[len(tempArray) - 1][1])
if (left == array[i][1]):
#print("LR")
if (i in idxArr):
break
else:
idxArr.append(i)
if (len(array) >= len(idxArr)):
tempArray.insert(0, array[i])
if (GetLengthOfArray(tempArray) > maxNum):
maxNum = GetLengthOfArray(tempArray)
if (len(array) >= len(idxArr)):
GetMaxLength(array, tempArray, tempArray[0][0], tempArray[len(tempArray) - 1][1])
if (right == array[i][0]):
#print("RL")
if (i in idxArr):
break
else:
idxArr.append(i)
if (len(array) >= len(idxArr)):
tempArray.append(array[i])
if (GetLengthOfArray(tempArray) > maxNum):
maxNum = GetLengthOfArray(tempArray)
if (len(array) >= len(idxArr)):
GetMaxLength(array, tempArray, tempArray[0][0], tempArray[len(tempArray) - 1][1])
if (right == array[i][1]):
#print("RR")
if (i in idxArr):
break
else:
idxArr.append(i)
SwitchPlaces(array[i])
if (len(array) >= len(idxArr)):
tempArray.append(array[i])
if (GetLengthOfArray(tempArray) > maxNum):
maxNum = GetLengthOfArray(tempArray)
if (len(array) >= len(idxArr)):
GetMaxLength(array, tempArray, tempArray[0][0], tempArray[len(tempArray) - 1][1])
#else:
# print("No condition BIG OOOF")
ReadInput()
SortArray(array)
MergeDominos(array)
for i in range(len(array)):
#print("iter num: ", i)
tempArray = []
idxArr = []
idxArr.append(i)
tempArray.append(array[i])
if (GetLengthOfArray(tempArray) > maxNum):
maxNum = GetLengthOfArray(tempArray)
GetMaxLength(array, tempArray, tempArray[0][0], tempArray[len(tempArray) - 1][1])
print(maxNum)
</code></pre>
<p><strong>E1</strong>:输入是以这种奇怪的方式进行的,因为列表的第一项给出了多米诺骨牌的数量,而且输入可以分为多行,然后我创建列表项对</p>
<p>输入示例:</p>
<pre><code>5 1 2
1 2
2 3
2
17
2 17
</code></pre>
<p>多米诺骨牌是:</p>
<pre><code>[('1','2'),('1','2'),('2','2'),('2','17'),('2','17')]
</code></pre>
<p>预期结果:</p>
<pre><code>5
</code></pre>
<p><em>(3,2)-(2,1)-(1,2)-(2,17)-(17-2)</em></p>