牛牛的跳跳棋 链接：https://ac.nowcoder.com/acm/contest/7604/B 来源：牛客网
牛牛最近在玩一种叫做跳跳棋的游戏，棋盘可以看成是一个一维的线性数组，编号从1到n+1。一开始牛牛的棋子位于第1个格子，游戏的最终目的是将棋子移动到第n+1个格子。棋盘1~n的每个格子都有一个“弹力系数”的权值pi。 当棋子位于第i个格子时，它的下一步可以移动到[i-pi,i+pi]范围内的任意一个格子。举例来说，假设第3个格子的弹力系数为2，那么牛牛下一步可以移动到第1,2,3,4,5格中的任意一格。现在给定1~n每格的弹力系数pi。牛牛发现，好像有时由于棋盘的pi设置不合理，导致游戏无法通关。 所以牛牛准备施展他神奇的魔法，他每次施展魔法都可以使得一个格子的弹力系数pi+1，他可以施展若干次魔法操作不同的格子，但是要求他不能够重复对一个格子施展魔法。 牛牛想要知道，为了使跳跳棋通关，他最少施展多少次魔法，并且他应该操作哪些格子。 请输出牛牛的最小操作次数，以及施展魔法的操作序列，操作序列的第i个数表示该次施展魔法的格子编号，由于答案不唯一，所以请你输出一个最小字典序的答案。
最小字典序指：在保证第1个数字尽可能小的前提下，保证第2个数字尽可能的小，然后在此前提下保证第3个数字尽可能的小…以此类推。 输入 12 5 4 3 3 2 1 0 0 0 1 0 0 输出 5 4 8 9 10 12 受同学邀请做题，开始没做出来，受到点播后，知道是使用贪心来做题，在两天陆陆续续的思考后，总算做出来了。 对于这道题，我们先看到移动的范围是[i-pi,i+pi],但是仔细思考之后，就可以发现这个i-pi是没有必要去使用的，也就是说一条路走到黑，能往前走就往前走，这里就是贪心策略。然后接着思考，如果对于两点i1、i2，假设i1+pi1==i2+pi2,那么我们对于i1和i2施法之后结果是一样的，两者都是向前走了一个格子，所以我们只要选择，两者之中比较小的一者来进行施法就可以了。我们用last变量表示能够到达最大距离同时序号最小的节点序号。
#include<cstdio> #include<iostream> #include<cmath> #include<vector> #include<stack> #include<cstring> #include<queue> #include<algorithm> using namespace std; typedef long long ll; int n; int a[100005]; int ans[100005]; int maxx=0,num=0; int last=1; int main(){ #ifdef LOCAL freopen(".\\a.in", "r", stdin); #endif scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); if(maxx>=n+1)break; if(a[i]+i>maxx){//大于最大值，不需要等于，以此来保证字典序最小 maxx=a[i]+i; last=i; } if(i==maxx){//说明这里已经不能走了，必须要进行施法 num++; ans[num]=last;//对last进行施法 last=i+1;//因为施法后最大距离为i+1，就不需要在i这里施法了 maxx++; } } printf("%d\n",num); for(int i=1;i<=num;i++){ printf("%d ",ans[i]); } return 0; }