$$\mathrm{牛牛的跳跳棋}$$

題目連結：$\mathrm{n}\mathrm{o}\mathrm{w}\mathrm{c}\mathrm{o}\mathrm{d}\mathrm{e}\mathrm{r}212985$

題目

牛牛最近在玩一種叫做跳跳棋的遊戲，棋盤可以看成是一個一維的線性陣列，編號從 $1$ 到 $n+1$ 。
一開始牛牛的棋子位於第 $1$ 個格子，遊戲的最終目的是將棋子移動到第 $n+1$ 個格子。
棋盤 $1\sim n$ 的每個格子都有一個「彈力系數」的權值 $p_i$。
當棋子位於第 $i$ 個格子時，它的下一步可以移動到 $[i-p_i,i+p_i]$ 範圍內的任意一個格子。
舉例來說，假設第 $3$ 個格子的彈力系數為 $2$ ，那麼牛牛下一步可以移動到第 $1,2,3,4,5$ 格中的任意一格。
現在給定 $1\sim n$ 每格的彈力系數 $p_i$ 。

牛牛發現，好像有時由於棋盤的 $p_i$ 設定不合理，導致遊戲無法通關。
所以牛牛準備施展他神奇的魔法，他每次施展魔法都可以使得一個格子的彈力系數 $p_i+1$，他可以施展若干次魔法操作不同的格子，但是要求他不能夠重複對一個格子施展魔法。
牛牛想要知道，為了使跳跳棋通關，他最少施展多少次魔法，並且他應該操作哪些格子。
請輸出牛牛的最小操作次數，以及施展魔法的操作序列，操作序列的第i個數表示該次施展魔法的格子編號，由於答案不唯一，所以請你輸出一個最小字典序的答案。

最小字典序指：在保證第 $1$ 個數位儘可能小的前提下，保證第 $2$ 個數位儘可能的小，然後在此前提下保證第 $3$ 個數位儘可能的小…以此類推。

輸入

第一行輸入一個正整數 $n$ 表示跳跳棋的格子數目。
接下來輸入一行 $n$ 個非負整數 $p_i$ 表示跳跳棋前 $n$ 個格子的彈力系數。

輸出

首先輸出一個非負整數 $ans$，表示少施展魔法的次數。
如果 $ans$ 不為 $0$，則再輸出一行 $ans$ 個整數表示需要施展魔法的格子編號，請給出一個最小字典序的答案。

樣例輸入1

12
5 4 3 3 2 1 0 0 0 1 0 0

樣例輸出1

5
4 8 9 10 12

樣例解釋1

除了 「4 8 9 10 12」 這個操作的答案序列以外， 「5 8 9 10 12」、「6 8 9 10 12」 也同樣是最小運算元下的答案。
但是 「4 8 9 10 12」 這個答案是字典序最小的，故輸出 「4 8 9 10 12」。

樣例輸入2

8
0 1 0 1 0 1 0 1

樣例輸出2

4
1 2 4 6

樣例輸入3

5
0 0 0 0 0

樣例輸出3

5
1 2 3 4 5

樣例解釋3

本樣例可以說明，不存在無解的情況，因為你至少可以令所有 $p_i$ 全都 +1。

樣例輸入4

5
1 1 1 1 1

樣例輸出4

0

資料範圍

對於 $20\%$ 的測試資料，保證 $1\le n\le 10$
對於 $40\%$ 的測試資料，保證 $0\le p_i\le 1$
對於 $100\%$ 的測試資料，保證 $1\le n\le 10^5,0\le p_i\le 100$

思路

這道題是一道貪心。

我們可以看出，往後走是沒有任何的必要的。
因為你走是可以走到 $[i-p_i,i+p_i]$ 中的任意一個點，那你走回去，再走回來，其實不如你直接往前走。

那這道題就可以很愉快的用貪心解決了，在用魔法之前竟可能的走到更前面，然後在跳最後一次的地方用一次魔法。

這時候可能會有人問：為什麼這樣一定可以呢？
因為它無論在什麼地方使用魔法，都只能在原來的基礎上多走一步，那肯定就是先找到能走到最遠地方的最後一點，然後再那個地方用魔法。

然後我們只要在走的時候記錄一下在那些地方用了魔法，在到終點之後輸出出來就可以了。

題目要求要字典序最小，那我們不往後走，而且如果有兩個地方都可以跳到最遠點，就選前面的那個。

考試時

之前好像有接觸過類似的題目，於是很快就看出來。
尋思了一會之後，就把它碼出來了。
得分：$100$ 分

程式碼

#include<cstdio>

using namespace std;

int n, a[100001], maxn = 1, maxx = 1, num[100001];

void write() {
    printf("%d\n", num[0]);
    for (int i = 1; i <= num[0]; i++) printf("%d ", num[i]);
}

int main() {
    scanf("%d", &n);
    
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        
        if (a[i]) {
            if (i + a[i] > maxn) {//貪心，在不魔法的情況下能走多遠走多遠 
                maxn = i + a[i];
                maxx = i;
                
                if (maxn > n) write();//可以走到終點了
            }
        }
        else if (i == maxn) {//已經儘可能的走的更遠了，一定要用魔法
            num[++num[0]] = maxx;
            maxn++;
            maxx = maxn;
            
            if (maxn > n) write();//用完魔法就到終點了
        }
    }
    
    return 0;
}