1840: 蓝桥杯2015年第六届真题-赢球票(3.13)

解题思路:模拟题目描述的过程,暴力法

注意事项:在遍历时要注意,因为每当索引与数字相同时都要,拿掉这张卡片,如果用数组存储卡片索引的话,要找到这张卡片并保证数组索引不越界较为困难和繁琐,换个思路--题目提到了顺时针顺序,而且每次只向后移动一格,是不是可以把卡片序列看成单链表呢?,每次拿掉一张卡片只需要修改前面节点的next指针指向当前节点的next指针,这个卡片(节点)在遍历时就不会被遍历到,当前卡片从逻辑上被删除了,这样就省去考虑如何指向下一张卡片的问题,因为地址都存在next指针里
参考代码:

import copy


class Node:#单链表结点类
    def __init__(self, val):
        self.val = val
        self.next = None

n = int(input().strip())
headv = Node(None)#生成虚拟头结点,便于后续对结点的操作(省去判断是否是头结点,因为头结点没有前驱结点,现在用虚拟结点来代替)
cur = headv
nums = []

for each in map(int, input().strip().split()):#读取输入.并生成单链表
    cur.next = Node(each)
    cur = cur.next
    nums.append(each)
    
cur.next = headv.next#让尾结点next指针指向头结点,因为单链表要遍历不止一次
max_gain = float("-inf")

for j in range(n):
    prev = copy.deepcopy(headv)#每次都要修改链表,所以拷贝副本,对副本操作
    cur = prev.next
    gain = 0
    i = 0
    temp = nums.copy() # 用于记录最大值
    
    while j: # 不同的开始位置
        prev = cur
        cur = cur.next
        j -= 1
        
    while temp and i < max(temp): # 如果i>数组中的最大值就结束,即不可能再得到卡片
        if cur.val == i + 1:
            temp.remove(i+1)
            gain += i+1
            i = 0
            prev.next = cur.next # 删除当前结点
            cur.next = None
            cur = prev.next
        else:
            i += 1
            prev = cur
            cur = cur.next
            
    max_gain = max(gain, max_gain)
    
print(max_gain)