1.3　赢球票(★)

题目信息

2016 年国赛-程序设计题

● C/C++ C组第4题

● Java C组第4题

【问题描述】

某机构举办球票大奖赛。获奖选手有机会赢得若干张球票。

主持人拿出 张卡片（上面写着 的数字），打乱顺序，排成一个圆圈。

你可以从任意一张卡片开始顺时针数数:

如果数到的数字刚好和卡片上的数字相同，则把该卡片收入囊中，从下一张卡片重新数数。

直到再无法收获任何卡片，游戏结束。囊中卡片数字的和就是赢得球票的张数。

比如卡片排列是 1 2 3，我们从 1 号卡开始数，就把 1 号卡拿走。再从 2 号卡开始，但数的数字无法与卡片对上，很快数字越来越大，不可能再拿走卡片了。因此这次我们只赢得了 1 张球票。

还不算太坏！如果我们开始就傻傻地从 2 或 3 号卡片数起，那就一张卡片都拿不到了。

如果运气好，卡片排列是 2 1 3，那我们可以顺利拿到所有的卡片！

本题目标：已知顺时针卡片序列，随便你从哪里开始数，求最多能赢多少张球票（就是收入囊中的卡片数字之和）。

【输入格式】

第一行一个整数 ，表示卡片数目。

第二行 个整数，表示顺时针排列的卡片。

【输出格式】

输出一行，一个整数，表示最好情况下能赢得多少张球票。

【样例输入】

3

1 2 3

【样例输出】

1

懒人速读

给定 张卡片，卡片上分别写着数字 。

现将这 张卡片围成一个圈。

我们可以从圈上任意一个位置开始顺时针数数： 。

若当前数到的数字和卡片上的数字相同，则将卡片取走，并从下一张卡片所在位置重新数数： 。

问我们取走的卡片上的数字之和最大可以是多少?

 

举例说明

若 ，则从第一张卡片所在位置开始数数的过程如下。

题目分析

核心考点

● 枚举

● 拆环成链

这是一道十分经典的模拟题。 刚着手解决本题时，可能绝大部分人都会提出4个问题。

问题1．题目给定的是一个环（圆圈），我们需要如何模拟在环上的移动呢?

问题2． 如何表示被拿走的卡片呢?

问题3．从哪个位置（起点）开始数数能拿走最多的卡片呢?

问题4．游戏什么时候会结束呢?

下面依次对这4个问题进行分析。

对于问题1：

对于在序列上的移动，如果想从当前位置顺时针移动到下一个位置，只要让下标 +1 即可。但当处于第 个位置时，由于没有第 个位置，所以无法移动。而对于环，第 个位置即第 1 个位置，所以从第 个位置移动到下一个位置只要让下标为 1 即可，其他位置的移动和序列相同。

对于问题2：

可以对被拿走的卡片打上标记。定义 ，其中 表示第 张是否被取走（ 表示被取走， 表示没有被取走）。下图展示了第 2 张卡片被拿走的情况。

对于问题3：

不知道。既然不知道，就将每个位置都作为一次起点并模拟整个过程，再从中选出最大的卡片和（即答案）。

对于问题4：

游戏结束分为以下两种情况。

● 取走所有的卡片（即取走 张卡片）。

● 当前数的数大于 （不可能再取走卡片了）。

解决了上述4个问题，就可以开始解题了。

按照上面的分析，我们需要完成以下几点。

(1) 枚举起点，并在每次枚举了一个起点后将所有卡片的 flag 初始化为 0。

(2) 有了起点后就可以模拟数数的过程，流程图如下。

● 判断游戏是否结束。

● 判断当前位置的卡片是否被取走（若被取走，则移动到下一个位置）。

● 判断当前位置的卡片的值是否和数的数的值相同（相同则取走该卡片，并重新开始数数）。

● 判断这次模拟得到的结果是否可以作为答案。

参考代码1-3　【赢球票】

 1   #include<bits/stdc++.h>
 2   using namespace std;
 3   const int N = 1e2 + 10;
 4   int n, a[N], flag[N];
 5   signed main(){
 6       cin >> n;
 7       for(int i = 1 ; i <= n ; i ++) cin >> a[i];
 8       int ans = 0; // ans 表示答案
 9       for(int i = 1 ; i <= n ; i ++){ // i 表示枚举的起点
10           // 将所有卡片的 flag 初始化为 0
11           for(int j = 1 ; j <= n ; j ++) flag[j] = 0; // flag[j] = 1 表示卡片被取走，反之没被取走
12           int num = 1 , pos = i , sum = 0, cnt = 0; // num 表示数的数的值，pos 表示当前位置，sum 表示以 i 为起点数数所能取走的卡片的和，cnt 表示拿走的卡片的数量
13   
14           // 开始模拟
15           while(1){
16               // 判断游戏是否结束
17               if(cnt == n || num > n) break; // 如果取走了所有卡片，或者数的数大于 n（不可能再取走卡片了），则游戏结束
18               // 判断当前位置的卡片是否被取走
19               if(flag[pos] == 1) { // 如果该卡片已被取走，则移动到下一个位置
20                   // 移动到下一个位置：如果当前位置 pos = n，则下一个位置为 1，否则下一个位置为 pos + 1
21                   if(pos == n) pos = 1;
22                   else pos ++;
23                   continue ;
24               }
25               // 数的数和当前位置卡片的值相同时取走该卡片（a[pos] 表示第pos张卡片的值）
26               if(num == a[pos]){
27                   sum += a[pos]; // 取走卡片的和 + a[pos]
28                   cnt ++;        // 取走的卡片个数 + 1
29                   num = 1;       // 取走卡片后要重新数数
30                   flag[pos] = 1; // 取走卡片后该卡片对应的 flag 置为 1
31                   // 移动到下一个位置：如果当前位置 pos = n，则下一个位置为 1，否则下一个位置为 pos + 1
32                   if(pos == n) pos = 1;
33                   else pos ++;
34               } else {
35                   // 数的数和当前位置卡片的值不相同时
36                   num ++ ; // 数的数的值 + 1
37                   // 移动到下一个位置：如果当前位置 pos = n，则下一个位置为 1，否则下一个位置为 pos + 1
38                   if(pos == n) pos = 1;
39                   else pos ++;
40               }
41           }
42           // 模拟结束，判断该模拟结果是否可以作为答案
43           if(sum > ans) ans = sum;
44       }
45       cout << ans << '\n';
46       return 0;
47   }