首页 > 代码库 > CODEVS2292（又是一道浪费时间的小题。。。）
CODEVS2292（又是一道浪费时间的小题。。。）
题目描述 Description
【Shadow 1】第二题
Shadow最近知道了图灵机是什么（Shadow：就是一行格子和一个机器头移来移去的呗！），于是他突发奇想，创造了一个新游戏——“图灵机游戏”（Shadow：好听吧？）。
游戏规则如下：
在一条长长的纸上有N个格子，每个格子上都有一个数，第i格的数记为Ai，机器头刚开始在第1格。这个游戏有两个操作：
1.如果现在在第i格，则可以移动机器头到第Ai格；
2.把某个Ai减少或增加1。
然而，fotile96看了之后却不以为然。“嗯，你挑战一下用最少次数使机器头到达第N格吧，这样好玩些……”
现在，Shadow已经快Crazy了。于是，Shadow把脸转向了你……
思路：进行广搜最短路，每次有三种状态：进行已知的位移，位置加一或减一。比较简单的广搜，但是一开始无奈的写错了程序，理解错了题意，1这个点第一次只能到a
[1]的位置，不能+1或-1，一开始就是因为没有理解好题，写出了tle一个点的东西。。。（可能是我的思路和实现的不一样。。。），然后就a了。。。
用一个数组标记这个点是否入队，只标记，不置反。这样能保证一个点的ans最优，同时避免了循环对列。
95分：
#include<iostream>#include<cstdio>#include<cstring>using namespace std;int que[5000001][3]={0},a[100001]={0},n,ll,ci[100001]={0};void bfs(){ int head,tail,tt,i; head=0;tail=1; que[1][0]=1; que[1][1]=a[1]; que[1][2]=0; ci[1]=0; while (head!=tail) { head=head%ll+1; if (que[head][0]!=que[head][1]) { tt=tail%ll+1; if (que[head][2]+1<ci[que[head][1]]) { ci[que[head][1]]=que[head][2]+1; tail=tail%ll+1; que[tail][0]=que[head][1]; que[tail][1]=a[que[tail][0]]; que[tail][2]=que[head][2]+1; } if (que[tail][0]==n) break; } if (que[head][1]<n&&que[head][2]+2<ci[que[head][1]+1]) { ci[que[head][1]]=que[head][2]+2; tail=tail%ll+1; que[tail][0]=que[head][0]; que[tail][1]=que[head][1]+1; que[tail][2]=que[head][2]+1; } if (que[head][1]>1&&que[head][2]+2<ci[que[head][1]-1]) { ci[que[head][1]]=que[head][2]+2; tail=tail%ll+1; que[tail][0]=que[head][0]; que[tail][1]=que[head][1]-1; que[tail][2]=que[head][2]+1; } }}int main(){ int i,j; memset(ci,127,sizeof(ci)); ll=5000000; scanf("%d",&n); for (i=1;i<=n;++i) scanf("%d",&a[i]); bfs(); printf("%d\n",ci[n]);}
100分：
#include<iostream>#include<cstdio>#include<cstring>using namespace std;int que[1000001]={0},a[100001]={0},n,ll,ci[100001]={0};bool use[100001]={false};void bfs(){ int head,tail,i; head=tail=1; que[1]=a[1]; ci[a[1]]=1; use[a[1]]=true; while (head<=tail) { if (que[head]==n) break; if (!use[a[que[head]]]) { tail=tail+1; que[tail]=a[que[head]]; ci[que[tail]]=ci[que[head]]+1; use[que[tail]]=true; } if (que[head]<n&&!use[que[head]+1]) { tail=tail+1; que[tail]=que[head]+1; ci[que[tail]]=ci[que[head]]+1; use[que[tail]]=true; } if (que[head]>1&&!use[que[head]-1]) { tail=tail+1; que[tail]=que[head]-1; ci[que[tail]]=ci[que[head]]+1; use[que[tail]]=true; } ++head; }}int main(){ int i,j; scanf("%d",&n); for (i=1;i<=n;++i) scanf("%d",&a[i]); bfs(); if (n==1) printf("0\n"); else printf("%d\n",ci[n]);}
CODEVS2292（又是一道浪费时间的小题。。。）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。