$$\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～n$ 的每个格子都有一个“弹力系数”的权值 $p_i$。
当棋子位于第 $i$ 个格子时，它的下一步可以移动到 $[i?p_i,i+p_i]$ 范围内的随便率性一格子。
举例来说，假设第 $3$ 个格子的弹力系数为 $2$ ，那么牛牛下一步可以移动到第 $1,2,3,4,5$ 格中的随便率性一。
如今给定 $1～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;
}