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

標(biāo)題鏈接：$\mathrm{n}\mathrm{o}\mathrm{w}\mathrm{c}\mathrm{o}\mathrm{d}\mathrm{e}\mathrm{r}212985$

標(biāo)題

牛牛比來在玩一種叫做跳跳棋的游戲，棋盤可以算作是一個(gè)一維的線性數(shù)組，編號大年夜 $1$ 到 $n+1$ 。
一開端牛牛的棋子位于第 $1$ 個(gè)格子，游戲的最注目標(biāo)是將棋子移動(dòng)到第 $n+1$ 個(gè)格子。
棋盤 $1～n$ 的每個(gè)格子都有一個(gè)“彈力系數(shù)”的權(quán)值 $p_i$。
當(dāng)棋子位于第 $i$ 個(gè)格子時(shí)，它的下一步可以移動(dòng)到 $[i?p_i,i+p_i]$ 范圍內(nèi)的隨便率性一格子。
舉例來說，假設(shè)第 $3$ 個(gè)格子的彈力系數(shù)為 $2$ ，那么牛牛下一步可以移動(dòng)到第 $1,2,3,4,5$ 格中的隨便率性一。
如今給定 $1～n$ 每格的彈力系數(shù) $p_i$ 。

牛牛發(fā)明，似乎有時(shí)因?yàn)槠灞P的 $p_i$ 設(shè)置不合理，導(dǎo)致游戲無法通關(guān)。
所以牛牛預(yù)備發(fā)揮他神奇的魔法，他每次發(fā)揮魔法都可以使得一個(gè)格子的彈力系數(shù) $p_i+1$，他可以發(fā)揮若干次魔法操作不合的格子，然則請求他不克不及夠反復(fù)對一個(gè)格子發(fā)揮魔法。
牛牛想要知道，為了使跳跳棋通關(guān)，他起碼發(fā)揮若干次魔法，并且他應(yīng)當(dāng)操作哪些格子。
請輸出牛牛的最小操作次數(shù)，以及發(fā)揮魔法的操作序列，操作序列的第i個(gè)數(shù)表示該次發(fā)揮魔法的格子編號，因?yàn)橹i底不獨(dú)一，所以請你輸出一個(gè)最小字典序的謎底。

最小字典序指：在包管第 $1$ 個(gè)數(shù)字盡可能小的前提下，包管第 $2$ 個(gè)數(shù)字盡可能的小，然后在此前提下包管第 $3$ 個(gè)數(shù)字盡可能的小…以詞攀類推。

輸入

第一行輸入一個(gè)正整數(shù) $n$ 表示跳跳棋的格子數(shù)量。
接下來輸入一行 $n$ 個(gè)非負(fù)整數(shù) $p_i$ 表示跳跳棋前 $n$ 個(gè)格子的彈力系數(shù)。

輸出

起首輸出一個(gè)非負(fù)整數(shù) $ans$，表示少發(fā)揮魔法的次數(shù)。
如不雅 $ans$ 不為 $0$，則再輸出一行 $ans$ 個(gè)整數(shù)表示須要發(fā)揮魔法的格子編號，請給出一個(gè)最小字典序的謎底。

樣例輸入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” 這個(gè)操作的謎底序列以外， “5 8 9 10 12”、“6 8 9 10 12” 也同樣是最小操作數(shù)下的謎底。
然則 “4 8 9 10 12” 這個(gè)謎底是字典序最小的，故輸出 “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

本樣例可以解釋，不存在無解的情況，因?yàn)槟阒辽倏梢粤钏?$p_i$ 全都 +1。

樣例輸入4

5
1 1 1 1 1

樣例輸出4

0

數(shù)據(jù)范圍

對于 $20\%$ 的測試數(shù)據(jù)，包管 $1\le n\le 10$
對于 $40\%$ 的測試數(shù)據(jù)，包管 $0\le p_i\le 1$
對于 $100\%$ 的測試數(shù)據(jù)，包管 $1\le n\le 10^5,0\le p_i\le 100$

思路

這道題是一道貪婪。

我們可以看出，往后走是沒有任何的須要的。
因?yàn)槟阕呤强梢宰叩?$[i?p_i,i+p_i]$ 中的隨便率性一個(gè)點(diǎn)，那你走歸去，再走回來，其實(shí)不如你直接往前走。

那這道題就可以很高興的用貪婪解決了，在用魔法之前竟可能的走到更前面，然后在跳最后一次的處所用一次魔法。

這時(shí)刻可能會(huì)有人問：為什么如許必定可以呢？
因?yàn)樗鼰o論在什么處所應(yīng)用魔法，都只能在本來的基本上多走一步，那肯定就是鍰煲到能走到最遠(yuǎn)處所的最后一點(diǎn)，然后再那個(gè)處所用魔法。

然后我們只要在走的時(shí)刻記錄一下在那些處所用了魔法，在到終點(diǎn)之后輸出出來就可以了。

標(biāo)題請求要字典序最小，那我們不往后走，并且如不雅有兩個(gè)處所都可以跳到最遠(yuǎn)點(diǎn)，就選前面的那個(gè)。

測驗(yàn)時(shí)

之前似乎有接觸過類似的標(biāo)題，于是很快就看出來。
沉思了一會(huì)之后，就把它碼出來了。
得分：$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) {//貪婪，在不魔法的情況下能走多遠(yuǎn)走多遠(yuǎn) 
                maxn = i + a[i];
                maxx = i;
                
                if (maxn > n) write();//可以走到終點(diǎn)了
            }
        }
        else if (i == maxn) {//已經(jīng)盡可能的走的更遠(yuǎn)了，必定要用魔法
            num[++num[0]] = maxx;
            maxn++;
            maxx = maxn;
            
            if (maxn > n) write();//用完魔法就到終點(diǎn)了
        }
    }
    
    return 0;
}