【蓝桥杯】43687.赢球票

题目形貌

某机构举行球票大奖赛。获奖选手有机会赢得若干张球票。
主持人拿出 N 张卡片（上面写着 1
⋯N 的数字），打乱顺序，排成一个圆圈。
你可以从任意一张卡片开始顺时针数数: 1
,2,3
⋯
⋯
如果数到的数字刚好和卡片上的数字相同，则把该卡片收入囊中，从下一个卡片重新数数。
直到再无法收获任何卡片，游戏结束。囊中卡片数字的和就是赢得球票的张数。
比如&#xff1
a;
卡片排列是&#xff1
a;1
2 3
我们从 1
号卡开始数，就把 1
号卡拿走。再从 2 号卡开始，但数的数字无法与卡片对上，很快数字越来越大，不大概再拿走卡片了。因此这次我们只赢得了 1
张球票。
还不算太坏&#xff01
;如果我们开始就傻傻地从 2 或 3 号卡片数起，那就一张卡片都拿不到了。
如果运气好，卡片排列是 2 1
3，那我们可以顺利拿到所有的卡片&#xff01
;
本题的目标&#xff1
a;已知顺时针卡片序列，随便你从哪里开始数，求最多能赢多少张球票（就是收入囊中的卡片数字之和）
输入形貌

第一行一个整数 N (N≤1
00)，表现卡片数量。
第二行 N 个整数，表现顺时针排列的卡片。
输出形貌
输出一行，一个整数，表现最好情况下能赢得多少张球票。
输入输出样例

示例
输入

1. 3
2. 1
3. 2 3

复制代码

输出

1. 1

复制代码

过程解析

  假设输入的卡片数量 N &#61
; 3，每张卡片的顺序是“1
，2，3”

[img]https://i-blog.csdnimg.cn/direct/cd8c564c1
8a241
539e61
c49a2bc7634f.png[/img]

  这时间，我们从1
的位置（index &#61
;&#61
; 0）开始数数，数到1
时，1
和卡片上的数字相称，则将卡片1
从卡池中取出，取出后，将该位置的卡片号码设置为0，卡池中剩下的卡牌酿成“2，3”。此时我们获得了1
张球票。

[img]https://i-blog.csdnimg.cn/direct/6205b7a7dd7a40be8bc585665a1
3ae07.png[/img]

  接着，再从2号卡开始，重新从1
开始数数，会发现剩下的都对不上，所以从1
开始取，最多只能取1
张票。
  卡的顺序稳定，我们从2的位置（index &#61
;&#61
; 1
）开始数数，会发现一张也拿不了。换个位置从3的位置开始数数，也是一张也拿不到。
  所以，在N &#61
; 3，每张卡片的顺序是“1
，2，3”的条件下，最多只能拿到1
张球票。
注意&#xff1
a;每一轮都要有一张卡牌被拿走，如果没有卡牌被拿走，则跳出内层循环进入外层循环。
  假设输入的卡片数量 N &#61
; 3，每张卡片的顺序换成是“2，1
，3”，看看会发生什么&#xff1
a;

  如果我们从2的位置（index &#61
;&#61
; 0）开始数数，第一次会把“3”这张卡拿走，将该位置的数字重置为0后，然后从2继承数，后面什么也拿不到。这种情况下最多只能拿到3张票。

[img]https://i-blog.csdnimg.cn/direct/d1
31
871
00bb341
6aa631
f5f5041
1
55db.png[/img]

  如果从1
的位置开始数数（index &#61
;&#61
; 1
），第一次会把“1
”这张卡拿走，并将该位置重置为0。此时获得的球票数为1
.

[img]https://i-blog.csdnimg.cn/direct/aa3f4be1
47d54068839bd776e3941
5b5.png[/img]

然后在3的位置（index &#61
;&#61
; 2），继承从1
开始数数，数到2时，将“2”这张卡片拿走，这时间就已经拿下了1
+ 2 &#61
; 3 张票，同时，将“2”这张卡片重置为0。

[img]https://i-blog.csdnimg.cn/direct/7eb63f5cf06443368e9dc5efc57ad731
.png[/img]

  最后剩下卡牌“3”，轮空两次后，数到“3”，将最后一张卡牌收入囊中，这时间所有卡牌被收下，一共获得了1
+2+3&#61
;6张球票。
  所以一样平常情况下，如果最后只剩下一张卡牌，是肯定可以拿完全部卡牌的。
  如果我们从3的位置（index &#61
;&#61
; 2）开始数数，来看看发生了什么&#xff1
a;
  第一次数到2的时间，会把卡牌2拿走，此时获得的球票数量为2。

[img]https://i-blog.csdnimg.cn/direct/dd4d5049ba034353bdb4f81
81
356d0c6.png[/img]

  接着数到“1
”的时间，把卡牌1
拿走，此时获得的球票数量为 2 + 1
&#61
; 3&#xff1
b;

[img]https://i-blog.csdnimg.cn/direct/d9a73d3691
6641
ddaa64f3fee655c627.png[/img]

  最后一步，把剩下的卡牌“3”拿走，此时获得的球票数量为 2 + 1
+ 3 &#61
; 6。

[img]https://i-blog.csdnimg.cn/direct/eb8f272c7fb1
405aade394fcabdcbd0e.png[/img]

  所以，当卡牌的顺序是“2，1
，3” 时，我们按位置顺序从前向后依次可以取得球票的数量是 [ 3, 6 , 6 ]，取得这个列表中的最大值，即为最好情况下能赢得球票的数量。
  再来看更加复杂一些的情况&#xff1
a;假设输入的卡片数量 N &#61
; 5，每张卡片的顺序是“3、1
、2、4、5”，来看看最多可以到的球票数&#xff1
a;

[img]https://i-blog.csdnimg.cn/direct/267945d8a6ea4551
b33295f1
d64a261
b.png[/img]

当从index &#61
;&#61
; 0 的位置开始数数的话，我们可以获得 4 + 5 &#61
; 9 张票&#xff1
b;
当从index &#61
;&#61
; 1
的位置开始数数的话，我们可以获得 1
张票&#xff1
b;
当从index &#61
;&#61
; 2 的位置开始数数的话，我们可以获得 0 张票&#xff1
b;
当从index &#61
;&#61
; 3 的位置开始数数的话，我们可以获得 3 + 1
&#61
; 4 张票&#xff1
b;
当从index &#61
;&#61
; 4 的位置开始数数的话，我们可以获得 0 张票&#xff1
b;
那么，数组 [ 9, 1
, 0, 4, 0 ] 中，最大的数就是9，说明该组合下最多获得9张票。
算法流程

[list=1
]

初始化&#xff1
a;
  N 表现卡片的数量，a是一个列表，用于存储卡片上的数字。
  sum_list 是一个长度为 N 的列表，用于存储从每个位置开始数数所能获得的球票数字之和，初始值都为 0。

外层循环
  使用 for i in range(N)遍历从每个位置开始数数的情况
  对于每个起始位置 i，举行如下操作:
  k表现当前正在操作的卡片位置，初始化为i。
  l 表现正在数的数字，初始化为 1
。
  b是 a的副本，用于操作而不影响原始的a 列表。

内层循环&#xff1
a;
  进入 while True 无穷循环，只要满足一定条件才会跳出。
  首先使用 while b[k] &#61
;&#61
; 0 来找到下一个未被拿走的卡片位置（由于 b[k] &#61
;&#61
; 0 表现该位置卡片已被拿走）。
  若 b[k] &#61
;&#61
; l&#xff1
a;
    说明数到的数字和当前位置的卡片数字相同，将该卡片数字添加到 sum_list 中。
    重置 l 为 1
，表现重新开始数数。
    将 b[k] 置为 0，表现该卡片已被拿走。
    检查 b 列表是否所有元素都为 0，如果是，说明所有卡片都已被拿走，结束该位置的循环。
  若 b[k]!&#61
; l&#xff1
a;
    l 加 1
，继承数下一个数字。
    无论是否匹配，都将 k 移动到下一个位置，使用 k &#61
; (k + 1
) % N 实现循环计数。
    若 l > N，说明数的数字已经超过卡片数量，结束该位置的循环。

结果输出&#xff1
a;
  使用 max(sum_list) 找出 sum_list 中的最大值，即为从不同位置开始数数所能获得的最多球票数。
代码实现

这是晏世琪同学提供的代码，注释掉print()语句后可以通过OJ&#xff1
a;

1. # 获取卡片数量 NN &#61
2. ; int(input())# 存储卡片上数字的列表a &#61
3. ; list(map(int, input().split()))# 用于存储从每个位置开始数能获得的球票数字之和，初始化为长度为 N 的全 0 列表sum_list &#61
4. ; [0] * Nfor i in range(N):    print(f"从位置 {i} 开始&#xff1
5. a;")    # 记录当前数数的起始位置    k &#61
6. ; i    # 初始化数数的数字为 1
7.     l &#61
8. ; 1
9.     # 创建一个与 a 列表相同的列表 b，用于操作，避免直接修改原列表 a    b &#61
10. ; a.copy()    while True:        print(f"当前位置 k&#xff1
11. a;{k}，数数数字 l&#xff1
12. a;{l}，列表 b&#xff1
13. a;{b}")        while b[k] &#61
14. ;&#61
15. ; 0:            # 如果当前位置的数字为 0，说明该位置的卡片已被拿走，将位置移动到下一个位置            k &#61
16. ; (k + 1
17. ) % N        if b[k] &#61
18. ;&#61
19. ; l:            # 如果数到的数字与当前位置的卡片数字相同            sum_list[i] +&#61
20. ; b[k]            print(f"在位置 {k} 找到匹配，将 {b[k]} 加到 sum_list[{i}] 中")            l &#61
21. ; 1
22.             b[k] &#61
23. ; 0            # 标记是否所有卡片都被拿走            all_zero &#61
24. ; True            for n in range(N):                if b[n]!&#61
25. ; 0:                    all_zero &#61
26. ; False                    break            if all_zero:                # 若所有卡片都被拿走，结束该位置的循环                print(f"所有卡片都已拿走，结束位置 {i} 的循环")                break        else:            l +&#61
27. ; 1
28.         k &#61
29. ; (k + 1
30. ) % N        if l > N:            # 若数数数字超过卡片数量，结束该位置的循环            print(f"数数数字超过 N，结束位置 {i} 的循环")            break# 找到最大的球票数字之和max_sum &#61
31. ; max(sum_list)print(max_sum)# print(sum_list.index(max_sum))

复制代码

这是别的一份通过OJ的&#xff1
a;

1. import osimport sysdef max_tickets(N, cards):    # 初始化sum数组，用于记录从每个起始位置开始数数能获得的球票总数    sum_tickets &#61
2. ; [0] * N        # 遍历所有大概的起始位置    for i in range(N):        k &#61
3. ; i  # 把i复制给k，由于数数一直在动，保存i的位置        l &#61
4. ; 1
5.   # l表现数数，从1
6. 开始数                # 创建一个暂时数组b来跟踪哪些卡片已经被取走        b &#61
7. ; cards[:]                while True:            # 跳过已经取走的卡片（即b[k] &#61
8. ;&#61
9. ; 0）            while b[k] &#61
10. ;&#61
11. ; 0:                k &#61
12. ; (k + 1
13. ) % N                        # 如果找到对应数字，累加到sum_tickets数组的sum_tickets[i]元素            if b[k] &#61
14. ;&#61
15. ; l:                sum_tickets[i] +&#61
16. ; b[k]                l &#61
17. ; 1
18.   # 每找到对应数字，将l置为1
19.                 b[k] &#61
20. ; 0  # 将该位置置为0                                # 判断数组里是否全部置为0                all_zero &#61
21. ; True                for n in range(N):                    if b[n] !&#61
22. ; 0:                        all_zero &#61
23. ; False                        break                                # 如果数组元素全部为0，制止本次i位置的查找                if all_zero:                    break            else:                # 如果没找到对应数字，将l+1
24.                 l +&#61
25. ; 1
26.                         k &#61
27. ; (k + 1
28. ) % N  # k每次查找都要循环+1
29.                         # 如果l大于N，制止本次i位置的查找            if l > N:                break        # 探求最大值    max_sum &#61
30. ; -1
31.     for i in range(N):        if max_sum < sum_tickets[i]:            max_sum &#61
32. ; sum_tickets[i]        return max_sum# 输入处置惩罚N &#61
33. ; int(input().strip())cards &#61
34. ; list(map(int, input().strip().split()))# 输出结果print(max_tickets(N, cards))

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao1
23.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。