题解 | #牛牛排队#

题目的主要信息：

一个环形的食堂， $n$ 个入口，入口处排队的人记录在数组a中
刚开始在第一个入口，如果有人在排队，花费1分钟走到下一个入口，如果下一个入口无人可直接进入，否则再花1分钟走到下一个入口，如此循环。（环形食堂，相当于数组a首尾相接）
每过1分钟每个入口排队的人会少1，问最终将从哪个入口进入

方法一：暴力模拟

具体做法：
我们可以设置一个变量i记录下标，设置一个变量time记录过去的时间，从第一个入口即下标i为0且time为0开始，我们检查 $a[i]-time$ 是否大于0，如果大于0，说明这个时间这个入口还有人在排队，否则这个口可以直接进入；如果不能直接进入，我们时间加1，下标加1（如果是到了数组a的末尾则置回0），如此循环直到找到第一个 $a[i]-time$ 小于等于0的入口。最后入口的序号是下标 $i+1$ 。
值得注意的是，我们先检查 $n=1$ 的情况只能从入口1进入， $n=2$ 的情况，只能从人数较少的入口进入。

class Solution {
public:
    int nowcoderQueue(int n, vector<int>& a) {
        if(n == 1) //只有1个入口，必定从1号进入
            return 1;
        if(n == 2){ //两个入口就从人少的那个进入
            if(a[0] < a[1])
                return 1;
            else
                return 0;
        }
        int i = 0; //记录入口的下标
        int time = 0; //记录等待的时间
        while(true){
            if(a[i] - time <= 0) //检查这个时间这个入口是否有人
                break;
            else{
                time++; //时间增加
                if(i != n - 1) //下标增加
                    i++;
                else
                    i = 0; //下标循环
            }
        }
        return i + 1; //返回的入口是最后的下标+1
    }
};

复杂度分析：

时间复杂度： $O(n+min(a_i))$ ，最坏情况下出现一个无人排队的情况需要循环 $min(a_i)$ 次，在此基础上最坏再循环 $n$ 次找到这个入口，所以复杂度不超过这个
空间复杂度： $O(1)$ ，常数级变量使用

方法二：按循环计算

具体做法：
因为这个是循环计算的，我们不必每次循环都去算，只需要计算每个数减少到0我们再次经过它需要循环的次数，取次数最少的就可以了，非第一个入口计算时我们还要减掉它的下标，因为它前面的在减少时他也在同步减少，要去掉这个偏差。我们公式计算时，先加 $n-1$ 再计算除法，保证向上取整。

图片说明

class Solution {
public:
    int nowcoderQueue(int n, vector<int>& a) {
        int res = 0;
        int m = (a[0] + n - 1) / n; //第一个数需要多少次循环到0
        for(int i = 1; i < n; i++){
            if(m > (a[i] - i + n - 1) / n){ //每个数减少到0的时间如果更小，因为前序关系必须严格大于符号
                m = (a[i] - i + n - 1) / n; //更迭更小的循环
                res = i;
            }
        }
        return res + 1;
    }
};

复杂度分析：

时间复杂度： $O(n)$ ，一次遍历
空间复杂度： $O(1)$ ，常数级空间