牛牛排队题解

下课了，牛牛要去食堂吃饭，他们学校的食堂有很多个门，而且整个建筑物是圆形的。只不过要去吃饭的人很多，在里面吃饭的人也很多，所以大家都在门口外面排队等待吃饭。
所以牛牛采取了这样的一个策略：刚开始时，牛牛在第一个门口，如果这个门口有人在排队，那么他选择花费1分钟时间走到下一个门口，如果没有人的话，牛牛就可以直接进去吃饭啦。食堂的每一个门，每1分钟排队的人数都会减少一个。
现在给你门的数量n，和每个门外排队的人的数量，如果按照牛牛的策略，那么牛牛最终会在哪个门进去吃饭呢？请你进行编程求解，返回牛牛最终是从第几个门进入食堂吃饭的。

时间复杂度
空间复杂度
解题策略：此题如果使用暴力求解，复杂度过高，容易超时。我们可以这么思考，利用题目的性质，找到一个规律，类似与贪心的思想：假设第i个门外一开始有a个人在排队，k是牛牛已经走过的圈数，我们假设牛牛在第k圈可以最终进入食堂，那么我们可以推出一道公式k∗n+i=a，所以我们只需要求解最小k所对应的i即可。
根据以上思路，代码如下:

const int INF = 0x3f3f3f3f;

/**
 * 返回牛牛最终是从第几个门进入食堂吃饭的
 * @param n int整型 代表门的数量
 * @param a int整型vector 代表每个门外等待的人数
 * @return int整型
 */
int solve(int n, vector<int> &a)
{
    // write code here
    int minn = INF;
    int ans = 1;
    for (int i = 0; i < n; i++)
    {
        int x = a[i] - i - 1 + n;
        if (minn > x / n)
        {
            minn = x / n;
            ans = i + 1;
        }
    }
    return ans;
}