C.牛牛摇骰子

题解

想到bfs，但是数据范围到1e9，内存和时间都会爆。为了优化，可以先考虑摇出一个较大的点数，尽可能多的摇出11，就可以尽快摇出这个点数。因此，猜测摇出某一点数的次数是有规律的（即，摇出大点数的次数可以由摇出小点数的次数直接算出）。
对于较小的数据打表，如下，其中第一行数据是摇出1-11所需要的次数，可以发现其中的规律：

    3    4    1    2    3    2    1    2    3    2    1
    4    3    2    3    4    3    2    3    4    3    2
    5    4    3    4    5    4    3    4    5    4    3
    6    5    4    5    6    5    4    5    6    5    4
    7    6    5    6    7    6    5    6    7    6    5
    8    7    6    7    8    7    6    7    8    7    6
    9    8    7    8    9    8    7    8    9    8    7
   10    9    8    9   10    9    8    9   10    9    8
   11   10    9   10   11   10    9   10   11   10    9
   12   11   10   11   12   11   10   11   12   11   10
   13   12   11   12   13   12   11   12   13   12   11
   14   13   12   13   14   13   12   13   14   13   12
   15   14   13   14   15   14   13   14   15   14   13
   16   15   14   15   16   15   14   15   16   15   14
   17   16   15   16   17   16   15   16   17   16   15
   18   17   16   17   18   17   16   17   18   17   16
   19   18   17   18   19   18   17   18   19   18   17
   20   19   18   19   20   19   18   19   20   19   18
   21   20   19   20   21   20   19   20   21   20   19
   22   21   20   21   22   21   20   21   22   21   20

代码

class Solution {
public:
    /**
     * 把所有询问的答案按询问顺序放入vector里
     * @param arr int整型vector 要查询坐标的数组
     * @return int整型vector
     */
    int a[11]={1,3,2,1,2,3,2,1,2,3,2};
    vector<int> MinimumTimes(vector<int>& arr) {
        // write code here
        vector<int> ans;
        for(int i=0;i<arr.size();++i)
        {
            int now=arr[i];
            if(now==2) ans.push_back(4);
            else ans.push_back(a[now%11]+(now-1)/11);
        }
        return ans;
    }
};