题目链接：

分析：

很容易想到用bfs，然而会超时，几乎是O(xt)了

这里用单调队列优化，

首先反着来，f[x] 为 x 要到1 的步数，f[1] = 0;

1、第一个条件就是 队列里面的元素个数小于t，

2、单调队列是个单调递减的队列。

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5  6 using namespace std; 7  8 const int maxn = 1000000 + 5; 9 int dis[maxn];10 int d[maxn];11 12 #define inf 0x3f3f3f3f13 14 int main()15 {16     int t;17     cin>>t;18     while(t--) {19         int x,k,t;20         cin>>x>>k>>t;21 22         int l,r;23 24         l = r = 1;25         dis[1] = 0;26         d[1] = 1;27 28         for(int j=2;j<=x;j++) {29             30             dis[j] = inf;31             32             while(l<=r&&d[l]
         
          =dis[j]) r--;36             d[++r] = j;37 38         }39 40         printf("%d\n",dis[x]);41     }42 43     return 0;44 }