題目描述

某機構舉辦球票大獎賽。獲獎選手有機會贏得若干張球票。

主持人拿出 N 張卡片（上面寫著 1?N 的數字），打亂順序，排成一個圓圈。

你可以從任意一張卡片開始順時針數數: 1,2,3
?
?

如果數到的數字剛好和卡片上的數字相同，則把該卡片收入囊中，從下一個卡片重新數數。

直到再無法收獲任何卡片，游戲結束。囊中卡片數字的和就是贏得球票的張數。

比如：

卡片排列是：1 2 3

我們從 1 號卡開始數，就把 1 號卡拿走。再從 2 號卡開始，但數的數字無法與卡片對上，很快數字越來越大，不可能再拿走卡片了。因此這次我們只贏得了 1 張球票。

還不算太壞！如果我們開始就傻傻地從 2 或 3 號卡片數起，那就一張卡片都拿不到了。

如果運氣好，卡片排列是 2 1 3，那我們可以順利拿到所有的卡片！

本題的目標：已知順時針卡片序列，隨便你從哪里開始數，求最多能贏多少張球票（就是收入囊中的卡片數字之和）

輸入描述

第一行一個整數 N (N≤100)，表示卡片數目。

第二行 N 個整數，表示順時針排列的卡片。

輸出描述
輸出一行，一個整數，表示最好情況下能贏得多少張球票。

輸入輸出樣例

示例
輸入

3
1 2 3

輸出

1

過程解析

??假設輸入的卡片數量 N = 3，每張卡片的順序是“1，2，3”

??這時候，我們從1的位置（index == 0）開始數數，數到1時，1和卡片上的數字相等，則將卡片1從卡池中取出，取出后，將該位置的卡片號碼設置為0，卡池中剩下的卡牌變成“2，3”。此時我們獲得了1張球票。

??接著，再從2號卡開始，重新從1開始數數，會發現剩下的都對不上，所以從1開始取，最多只能取1張票。
??卡的順序不變，我們從2的位置（index == 1）開始數數，會發現一張也拿不了。換個位置從3的位置開始數數，也是一張也拿不到。
??所以，在N = 3，每張卡片的順序是“1，2，3”的條件下，最多只能拿到1張球票。

注意：每一輪都要有一張卡牌被拿走，如果沒有卡牌被拿走，則跳出內層循環進入外層循環。

??假設輸入的卡片數量 N = 3，每張卡片的順序換成是“2，1，3”，看看會發生什么：

??如果我們從2的位置（index == 0）開始數數，第一次會把“3”這張卡拿走，將該位置的數字重置為0后，然后從2繼續數，后面什么也拿不到。這種情況下最多只能拿到3張票。

??如果從1的位置開始數數（index == 1），第一次會把“1”這張卡拿走，并將該位置重置為0。此時獲得的球票數為1.

然后在3的位置（index == 2），繼續從1開始數數，數到2時，將“2”這張卡片拿走，這時候就已經拿下了1+ 2 = 3 張票，同時，將“2”這張卡片重置為0。

??最后剩下卡牌“3”，輪空兩次后，數到“3”，將最后一張卡牌收入囊中，這時候所有卡牌被收下，一共獲得了1+2+3=6張球票。
??所以一般情況下，如果最后只剩下一張卡牌，是肯定可以拿完全部卡牌的。

??如果我們從3的位置（index == 2）開始數數，來看看發生了什么：
??第一次數到2的時候，會把卡牌2拿走，此時獲得的球票數量為2。

??接著數到“1”的時候，把卡牌1拿走，此時獲得的球票數量為 2 + 1 = 3；

??最后一步，把剩下的卡牌“3”拿走，此時獲得的球票數量為 2 + 1 + 3 = 6。

??所以，當卡牌的順序是“2，1，3” 時，我們按位置順序從前向后依次可以取得球票的數量是 [ 3, 6 , 6 ]，取得這個列表中的最大值，即為最好情況下能贏得球票的數量。

??再來看更加復雜一些的情況：假設輸入的卡片數量 N = 5，每張卡片的順序是“3、1、2、4、5”，來看看最多可以到的球票數：

當從index == 0 的位置開始數數的話，我們可以獲得 4 + 5 = 9 張票；
當從index == 1 的位置開始數數的話，我們可以獲得 1 張票；
當從index == 2 的位置開始數數的話，我們可以獲得 0 張票；
當從index == 3 的位置開始數數的話，我們可以獲得 3 + 1 = 4 張票；
當從index == 4 的位置開始數數的話，我們可以獲得 0 張票；
那么，數組 [ 9, 1, 0, 4, 0 ] 中，最大的數就是9，說明該組合下最多獲得9張票。

算法流程

1. 初始化：
   ??N 表示卡片的數量，a是一個列表，用于存儲卡片上的數字。
   ??sum_list 是一個長度為 N 的列表，用于存儲從每個位置開始數數所能獲得的球票數字之和，初始值都為 0。
2. 外層循環
   ??使用 for i in range(N)遍歷從每個位置開始數數的情況
   ??對于每個起始位置 i，進行如下操作:
   ??k表示當前正在操作的卡片位置，初始化為i。
   ??l 表示正在數的數字，初始化為 1。
   ??b是 a的副本，用于操作而不影響原始的a 列表。
3. 內層循環：
   ??進入 while True 無限循環，只要滿足一定條件才會跳出。
   ??首先使用 while b[k] == 0 來找到下一個未被拿走的卡片位置（因為 b[k] == 0 表示該位置卡片已被拿走）。
   ??若 b[k] == l：
   ????說明數到的數字和當前位置的卡片數字相同，將該卡片數字添加到 sum_list[i] 中。
   ????重置 l 為 1，表示重新開始數數。
   ????將 b[k] 置為 0，表示該卡片已被拿走。
   ????檢查 b 列表是否所有元素都為 0，如果是，說明所有卡片都已被拿走，結束該位置的循環。
   ??若 b[k]!= l：
   ????l 加 1，繼續數下一個數字。
   ????無論是否匹配，都將 k 移動到下一個位置，使用 k = (k + 1) % N 實現循環計數。
   ????若 l > N，說明數的數字已經超過卡片數量，結束該位置的循環。
4. 結果輸出：

??使用 max(sum_list) 找出 sum_list 中的最大值，即為從不同位置開始數數所能獲得的最多球票數。

代碼實現

這是晏世琪同學提供的代碼，注釋掉print()語句后可以通過OJ：

# 獲取卡片數量 N
N = int(input())
# 存儲卡片上數字的列表
a = list(map(int, input().split()))
# 用于存儲從每個位置開始數能獲得的球票數字之和，初始化為長度為 N 的全 0 列表
sum_list = [0] * Nfor i in range(N):print(f"從位置 {i} 開始：")# 記錄當前數數的起始位置k = i# 初始化數數的數字為 1l = 1# 創建一個與 a 列表相同的列表 b，用于操作，避免直接修改原列表 ab = a.copy()while True:print(f"當前位置 k：{k}，數數數字 l：{l}，列表 b：{b}")while b[k] == 0:# 如果當前位置的數字為 0，說明該位置的卡片已被拿走，將位置移動到下一個位置k = (k + 1) % Nif b[k] == l:# 如果數到的數字與當前位置的卡片數字相同sum_list[i] += b[k]print(f"在位置 {k} 找到匹配，將 {b[k]} 加到 sum_list[{i}] 中")l = 1b[k] = 0# 標記是否所有卡片都被拿走all_zero = Truefor n in range(N):if b[n]!= 0:all_zero = Falsebreakif all_zero:# 若所有卡片都被拿走，結束該位置的循環print(f"所有卡片都已拿走，結束位置 {i} 的循環")breakelse:l += 1k = (k + 1) % Nif l > N:# 若數數數字超過卡片數量，結束該位置的循環print(f"數數數字超過 N，結束位置 {i} 的循環")break
# 找到最大的球票數字之和
max_sum = max(sum_list)
print(max_sum)
# print(sum_list.index(max_sum))

這是另外一份通過OJ的：

import os
import sysdef max_tickets(N, cards):# 初始化sum數組，用于記錄從每個起始位置開始數數能獲得的球票總數sum_tickets = [0] * N# 遍歷所有可能的起始位置for i in range(N):k = i  # 把i復制給k，因為數數一直在動，保存i的位置l = 1  # l表示數數，從1開始數# 創建一個臨時數組b來跟蹤哪些卡片已經被取走b = cards[:]while True:# 跳過已經取走的卡片（即b[k] == 0）while b[k] == 0:k = (k + 1) % N# 如果找到對應數字，累加到sum_tickets數組的sum_tickets[i]元素if b[k] == l:sum_tickets[i] += b[k]l = 1  # 每找到對應數字，將l置為1b[k] = 0  # 將該位置置為0# 判斷數組里是否全部置為0all_zero = Truefor n in range(N):if b[n] != 0:all_zero = Falsebreak# 如果數組元素全部為0，停止本次i位置的查找if all_zero:breakelse:# 如果沒找到對應數字，將l+1l += 1k = (k + 1) % N  # k每次查找都要循環+1# 如果l大于N，停止本次i位置的查找if l > N:break# 尋找最大值max_sum = -1for i in range(N):if max_sum < sum_tickets[i]:max_sum = sum_tickets[i]return max_sum# 輸入處理
N = int(input().strip())
cards = list(map(int, input().strip().split()))# 輸出結果
print(max_tickets(N, cards))