牛牛的跳跳棋 ? \operatorname{牛牛的跳跳棋} 牛牛的跳跳棋

題目鏈接： nowcoder 212985 ? \operatorname{nowcoder\ 212985} nowcoder 212985

題目

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

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

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

輸入

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

輸出

首先輸出一個非負整數 a n s ans ans，表示少施展魔法的次數，
如果 a n s ans ans 不為 0 0 0，則再輸出一行 a n s ans 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 p_i pi? 全都 +1，

樣例輸入4

5
1 1 1 1 1

樣例輸出4

0

資料范圍

對于 20 % 20\% 20% 的測驗資料，保證 1 ≤ n ≤ 10 1 \leq n \leq 10 1≤n≤10
對于 40 % 40\% 40% 的測驗資料，保證 0 ≤ p i ≤ 1 0 \leq p_i \leq 1 0≤pi?≤1
對于 100 % 100\% 100% 的測驗資料，保證 1 ≤ n ≤ 1 0 5 , 0 ≤ p i ≤ 100 1 \leq n \leq 10^5,0 \leq p_i \leq 100 1≤n≤105,0≤pi?≤100

思路

這道題是一道貪心，

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

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

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

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

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

考試時

之前好像有接觸過類似的題目，于是很快就看出來，
尋思了一會之后，就把它碼出來了，
得分： 100 100 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;
}