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   }