3597: 牛牛的跳跳棋(第一轮02)

内存限制:128 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:2 解决:1

题目描述

牛牛最近在玩一种叫做跳跳棋的游戏,棋盘可以看成是一个一维的线性数组,编 号从 1 到 n+1。 一开始牛牛的棋子位于第 1 个格子,游戏的最终目的是将棋子移动到第 n+1 个 格子。 棋盘 1~n 的每个格子都有一个“弹力系数”的权值𝑝𝑖。 当棋子位于第 i 个格子时,它的下一步可以移动到[𝑖 − 𝑝𝑖 , 𝑖 + 𝑝𝑖 ]范围内的任意一 个格子。 举例来说,假设第 3 个格子的弹力系数为 2,那么牛牛下一步可以移动到第 1,2,3,4,5 格中的任意一格。 现在给定 1~n 每格的弹力系数𝑝𝑖 牛牛发现,好像有时由于棋盘的𝑝𝑖设置不合理,导致游戏无法通关。 所以牛牛准备施展他神奇的魔法,他每次施展魔法都可以使得一个格子的弹力系 数𝑝𝑖 + 1,他可以施展若干次魔法操作不同的格子,但是要求他不能够重复对一 个格子施展魔法。 牛牛想要知道,为了使跳跳棋通关,他最少施展多少次魔法,并且他应该操作哪 些格子。 请输出牛牛的最小操作次数,以及施展魔法的操作序列,操作序列的第 i 个数表 示该次施展魔法的格子编号,由于答案不唯一,所以请你输出一个最小字典序的 答案。 最小字典序指:在保证第 1 个数字尽可能小的前提下,保证第 2 个数字尽可能的 小,然后在此前提下保证第 3 个数字尽可能的小....以此类推。

输入

第一行输入一个正整数 n 表示跳跳棋的格子数目。 接下来输入一行 n 个非负整数𝑝𝑖表示跳跳棋前 n 个格子的弹力系数。

输出

首先输出一个非负整数 ans,表示少施展魔法的次数。 如果 ans 不为 0,则再输出一行 ans 个整数表示需要施展魔法的格子编号,请给 出一个最小字典序的答案。

样例输入 复制

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

样例输出 复制

4
4 8 9 10 

提示

【样例 1 输入】 

12 

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

【样例 1 输出】

 5 

4 8 9 10 12 

【样例 1 说明】 

除了"4 8 9 10"这个操作的答案序列以外,"5 8 9 10 ","6 8 9 10 "也同样是 最小操作数下的答案。 但是"4 8 9 10 "这个答案是字典序最小的,故输出"4 8 9 10 "。 

【样例 2 输入】 

8

0 1 0 1 0 1 0 1 

【样例 2 输出】 

1 2 4 6 

【样例 3 输入】

 5 

0 0 0 0 0 

【样例 3 输出】

 5 

1 2 3 4 5 

【样例 3 说明】 本样例可以说明,不存在无解的情况,因为你至少可以令所有𝑝𝑖全都+1。 

【样例 4 输入】 

5

 1 1 1 1 1

 【样例 4 输出】

 0 

【数据范围】

 对于20%的测试数据,保证1 ≤ 𝑛 ≤ 10 对于40%的测试数据,保证≤ 𝑝𝑖 ≤ 1 对于100%的测试数据,保证1 ≤ 𝑛 ≤ 105 ,0 ≤ 𝑝𝑖 ≤ 100

来源/分类