题意：

给你一个无限长的数轴，刚开始你在位置 $0$ 处，你每次可以向左或者向右移动 $3,7,11$ 个单位，现在有 $n$ 次询问，第 $i$ 次询问给你一个数字 $arr[i]$ ，问从起点位置到 $arr[i]$ 所在位置最少需要多少步？

解法一（最短路，不可AC）

显然我们可以根据题意构建一张以数轴上的数字为点，边权为 $1$ 的无向图，边 $(u,v)$ 表示数字 $u$ 变化成数字 $v$ 的一次操作

那么对于第 $i$ 个询问 $arr[i]$ ，答案为起点 $0$ 到点 $arr[i]$ 的最短路

代码：

class Solution {
public:
    vector<int> MinimumTimes(vector<int>& arr) {
        int mx_q=0;//询问最大的数字
        for(auto& x:arr){
            mx_q=max(mx_q,x);//求解询问最大的数字
        }
        mx_q+=20;//由于可以向左走，且一次最多走11个单位，故将范围扩大20
        vector<int> dis(mx_q+1,0x3f3f3f3f);//动态分配内存，且初始化一个极大值
        vector<int>* gr=new vector<int>[mx_q+1];//邻接表存图，动态内存分配
        for(int i=0;i<=mx_q;i++){//对于每个点向周围连边
            if(i+3<=mx_q){
                //向右走3
                gr[i].push_back(i+3);
                gr[i+3].push_back(i);
            }
            if(i+7<=mx_q){
                //向右走7
                gr[i].push_back(i+7);
                gr[i+7].push_back(i);
            }
            if(i+11<=mx_q){
                //向右走11
                gr[i].push_back(i+11);
                gr[i+11].push_back(i);
            }
            if(i-3>=0){
                //向左走3
                gr[i].push_back(i-3);
                gr[i-3].push_back(i);
            }
            if(i-7>=0){
                //向左走7
                gr[i].push_back(i-7);
                gr[i-7].push_back(i);
            }
            if(i-11>=0){
                //向左走11
                gr[i].push_back(i-11);
                gr[i-11].push_back(i);
            }
        }
        queue<int> que;//bfs队列
        que.push(0);//起点
        dis[0]=0;
        while(!que.empty()){
            int x=que.front();
            que.pop();
            for(auto v:gr[x]){
               if(dis[v]>dis[x]+1){
                   //松弛操作
                   dis[v]=dis[x]+1;
                   que.push(v);
               }
            }
        }
        vector<int> ans;
        for(auto x:arr){
            //记录答案
            ans.push_back(dis[x]);
        }
        return ans;
    }
};

时间复杂度： $O(max\{a_i\})$ ，总共有 $O(max\{a_i\})$ 级别个点，BFS求解每个点只会访问一次，故总的时间复杂度为 $O(max\{a_i\})$

空间复杂度： $O(max\{a_i\}+n)$ ，邻接表存图，距离数组，队列的空间大小都是 $O(max\{a_i\})$ 级别的，答案数组的空间大小为 $O(n)$ 级别的，故总的空间复杂度为 $O(max\{a_i\}+n)$

解法二（取模优化）

我们知道当 $arr[i]$ 足够大时，肯定是先走很多步11，直到走到距离 $arr[i]$ 足够近时，再走小的步数进行微调

于是我们可以对一个较小的距离范围求解最短路

然后对于一个询问，我们可以枚举最后一段的长度，前面的长度全部用步数11的方法走，最后取最小的步数即可

代码：

class Solution {
public:
    /**
     * 把所有询问的答案按询问顺序放入vector里
     * @param arr int整型vector 要查询坐标的数组
     * @return int整型vector
     */
    int dis[31];//30>=2*11，足够小的范围
    vector<int> gr[31];//邻接表存图
    vector<int> MinimumTimes(vector<int>& arr) {
        memset(dis,0x3f,sizeof dis);//初始化一个极大值
        for(int i=0;i<=30;i++){
            gr[i].clear();//多测清空
        }
        for(int i=0;i<=30;i++){
            //枚举每个点
            if(i+3<=30){
                //向右走3
                gr[i].push_back(i+3);
                gr[i+3].push_back(i);
            }
            if(i+7<=30){
                //向右走7
                gr[i].push_back(i+7);
                gr[i+7].push_back(i);
            }
            if(i+11<=30){
                //向右走11
                gr[i].push_back(i+11);
                gr[i+11].push_back(i);
            }
            if(i-3>=0){
                //向左走3
                gr[i].push_back(i-3);
                gr[i-3].push_back(i);
            }
            if(i-7>=0){
                //向左走7
                gr[i].push_back(i-7);
                gr[i-7].push_back(i);
            }
            if(i-11>=0){
                //向左走11
                gr[i].push_back(i-11);
                gr[i-11].push_back(i);
            }
        }
        dis[0]=0;
        queue<int> que;
        que.push(0);
        while(!que.empty()){
            int x=que.front();
            que.pop();
            for(auto v:gr[x]){
                if(dis[v]>dis[x]+1){
                    //松弛操作
                    dis[v]=dis[x]+1;
                    que.push(v);
                }
            }
        }
        vector<int> ans;
        for(auto x:arr){
            int res=0x3f3f3f3f;
            for(int k=0;k<=2;k++){
                //枚举一共走多少个11
                if(x>=k*11){
                   //x/11-k为走的11的个数
                   res=min(res,dis[x-(x/11-k)*11]+(x/11-k));
                }
            }
            ans.push_back(res);
        }
        return ans;
    }
};

时间复杂度： $O(n)$ ，由于预处理点的数量只有31个，故建图和BFS求解最短路的时间复杂度为 $O(1)$ ，有 $n$ 次询问，每次询问的复杂度都为 $O(1)$ ，故总的时间复杂度为 $O(n)$

空间复杂度： $O(n)$ ，邻接表存图，距离数组，队列所占空间都为 $O(1)$ 级别，答案数组的空间为 $O(n)$ 级别，故总的空间复杂度为 $O(n)$

题解 | #牛牛摇骰子#

题意：

解法一（最短路，不可AC）

解法二（取模优化）