页【BFS】

题目大意： 给出 n n （nn为3,5,7,9中的一个数）个在160至190的数字，每次可以把中间的数字放到最左边或最右边，求这个序列成为单调递增的最少次数。 Input I n p u t

3 179 173 175

Output O u t p u t

2

---

思路：

思路一：贪心

哇！ n≤9 n ≤ 9 诶！好开心啊！贪心一定能过吧！ 然而并不可以。。。 贪心有很大几率死循环。比如说： Input I n p u t

5 2 1 3 5 4

左边三个数就永远死循环。 贪心代码：

#include <cstdio> #include <iostream> #include <algorithm> using namespace std; int n,mid,m,t,a[101],b[101],k; int pd() { for (int i=2;i<=n;i++) if (a[i]<a[i-1]) return 1; return 0; } int main() { scanf("%d",&n); for (int i=1;i<=n;i++) { scanf("%d",&a[i]); b[i]=a[i]; } sort(b+1,b+1+n); m=(1+n)/2; mid=b[m]; while (pd()) { k++; if (a[m]<mid) { t=a[m]; for (int i=m;i>1;i--) a[i]=a[i-1]; a[1]=t; } else { t=a[m]; for (int i=m;i<n;i++) a[i]=a[i+1]; a[n]=t; } } printf("%d\n",k); return 0; }

思路二：DFS

贪心有可能无法搞定，但是如果DFS求出所有答案，再取最优值，肯定 没问题 TLE。 但是至少比0分好吧。

（仅仅是思路，代码未打完）

思路三：BFS

仔细一看，这题其实是要我们求最优解，那么自然会想到DP和BFS。由于数据规模小，所以大部分可能是BFS。

那么首先要解决BFS判重问题。贪心不用判重，但是BFS肯定要。自然而然的可以想到HASH，但是这里介绍另一种方法—— map m a p 库。

map m a p 库是 STL S T L 中的一个。它的最常见用法是定义一个下标可以为任何类型（包括 string s t r i n g ， char c h a r ， double d o u b l e 等等），范围巨大的数组。（不会MLE）

例如

map<string,int> a;

表示定义一个下标为 string s t r i n g 类型，变量类型为 int i n t 的无限大数组 a a 。定义了这个数组之后，就可以与正常用法一样使用它。例如：

a["Hello_world"]=2333;

然后既然mapmap是一个库，那么自然也要加上头文件

#include <map>

那么回到这道题，我们可以设定一个 map m a p 数组 p p ，即 map<int,int>pmap<int,int>p ，那么只要我们能把160到190的数字”压缩“成一位数，就好啦！（因为这样即使 n=9 n = 9 ，9个数字连起来也就9位数， int i n t 的范围是十位数，就不会爆）

那么应该怎么压缩呢？

可以用到离散化的思想，将最小的数对应1，次小的数对应2······最大的数对应 n n ，就把三位数压缩成了一位数。而且这里的离散化并不麻烦，n≤9n≤9，可以用 O(n2) O ( n 2 ) 的方法对应。

那么判重搞定了，接下来就是BFS的问题了。

不难想到，变化总数最多只有 9! 9 ! 次，所以数组开到 9! 9 ! 就可以了。

然后对于每一种情况，我们可以把中间的数字放到最左边或最右边，那么可以在移动前先判断移动后的结果是否会与之前的重复，重复就不移动， tail−− t a i l − − ，不重复就移动， father f a t h e r 数组更新， state s t a t e 记录答案。

移动后就判断是否单调，单调的话就递归输出答案，否则继续搜索。

注意：最终如果无法完成一定要输出” NoAnswer N o A n s w e r ”！！！

---

代码：

#include <cstdio> #include <iostream> #include <algorithm> #include <map> using namespace std; int n,a[101],b[101],head,tail,father[363080],state[13][363080],sum,mid; //9！=362880 map<int,int> p; int pd_l() //判断是否可以往左移 { int o=state[mid][head]; for (int i=1;i<=n;i++) if (i!=mid) o=o*10+state[i][head]; return o; } int pd_r() //判断是否可以往右移 { int o=0; for (int i=1;i<=n;i++) if (i!=mid) o=o*10+state[i][head]; o=o*10+state[mid][head]; return o; } void left() //左移 { father[tail]=head; for (int i=1;i<=n;i++) state[i][tail]=state[i][head]; //先全部赋值给head int t=state[mid][head]; for (int i=mid;i>1;i--) //更改 state[i][tail]=state[i-1][tail]; state[1][tail]=t; } void right() //右移，同左移 { father[tail]=head; for (int i=1;i<=n;i++) state[i][tail]=state[i][head]; int t=state[mid][head]; for (int i=mid;i<n;i++) state[i][tail]=state[i+1][tail]; state[n][tail]=t; } void print(int x) //递归输出 { if (father[x]!=-1) print(father[x]); sum++; return; } int OK() //判断是否单调递增 { for (int i=2;i<=n;i++) if (state[i][tail]<state[i-1][tail]) return 0; print(tail); printf("%d\n",sum-1); return 1; } void bfs() //广搜 { head=0; tail=1; father[1]=-1; for (int i=1;i<=n;i++) state[i][1]=a[i]; //初始化 do { head++; tail++; int q=pd_l(); //往左移 if (!p[q]) { p[q]=1; left(); if (OK()) return; } else tail--; tail++; q=pd_r(); //往右移 if (!p[q]) { p[q]=1; right(); if (OK()) return; } else tail--; } while (head<tail); puts("No Answer"); //没有答案 return; } int main() { scanf("%d",&n); mid=(1+n)/2; for (int i=1;i<=n;i++) { scanf("%d",&a[i]); b[i]=a[i]; } for (int i=2;i<=n;i++) //特判，开始是否已经单调递增 { if (a[i]<a[i-1]) break; if (i==n) { printf("0\n"); return 0; } } sort(b+1,b+1+n); //排序，为离散化做准备 for (int i=1;i<=n;i++) //离散化 for (int j=1;j<=n;j++) if (b[i]==a[j]) { a[j]=i; break; } bfs(); return 0; }