NC645 题解 | #牛牛排队#

题意分析

简明题意，给我们一个数组，这个数组的每个位置都有一个数字，一个人从1开始循环遍历这个数字，每遍历一个位置，这个数组的所有的数字都会减少1，直到为0.问这个人第一次遇到数字为0的位置的下标。数组的大小最大为1e5，每个位置的数字最大为1e9

思路分析

我们首先知道，如果我们直接对这个数字进行遍历，那么肯定是会被TLE的，所以我们需要进行优化，我们发现，如果不管其他的，那么我们每个位置到达0的时候的需要遍历的轮数是固定的，所以我们可以预先处理出所有的位置，遍历这个位置，而且这个位置的数字为0的最小轮数。对于某一个数字x,我们发现一定需要遍历的轮数是x/n,然后会出现一个余数，我们发现，如果这个余数不小于这个位置，那么说明我们需要多遍历两轮，否则，我们只需要多遍历一轮即可。预处理之后，我们找到最小的轮数第一次出现的位置即可。

alt

解法一 C++版本

代码如下
- 需要遍历整个数组，时间复杂度为 $O (n)$
- 用一个数组存储了所有的位置所需要的轮数，空间复杂度为 $O (n)$

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回牛牛最终是从第几个门进入食堂吃饭的
     * @param n int整型 代表门的数量
     * @param a int整型vector 代表每个门外等待的人数
     * @return int整型
     */
    int nowcoderQueue(int n, vector<int>& a) {
        // write code here
        vector<int> b(n+1);
        
        int mi=1e9+7;  // 用来记录最少的轮数
        for(int i=0;i<n;i++){
            b[i]=a[i]/n;
            int more=a[i]%n;  
            if(more>=i+1) b[i]+=2;  // 如果余数超过了当前的位置，那么说明需要下一轮的时候才能为0
            else b[i]++;  // 如果余数没有超过当前的位置，那么说明当前这轮就能轮完
            mi=min(mi,b[i]);   // 记录最小的值
        }
        
        int ans=0;
        for(int i=0;i<n;i++){
            if(b[i]==mi){  // 找到第一个最小值的位置就是答案
                ans=i+1;
                break;
            }
        }
        
        return ans;
    }
};

解法二 Go语言版本

我们从上面的一种解法进行一个优化，我们发现，我们其实没有必要开一个b数组，在中途用一个临时变量存储即可，然后维护最小值和更新最小的的第一次出现的位置即可。
代码如下
- 需要遍历整个数组，时间复杂度为 $O (n)$
- 过程中只开了几个变量，空间复杂度为 $O (1)$

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 返回牛牛最终是从第几个门进入食堂吃饭的
 * @param n int整型 代表门的数量
 * @param a int整型一维数组 代表每个门外等待的人数
 * @return int整型
*/
func nowcoderQueue( n int ,  a []int ) int {
    // write code here
    
    mi := 1000000007
    ans := 0
    for i := 0; i < n; i++ {
        // 我们发现没必要用数组存储每个值，所以我们开一个中间变量临时存储即可
        tmp := a[i]/n;
        // 如果余数超过了这个位置
        if(a[i]%n>=i+1){
            tmp+=2;
        }else{
            // 如果余数没有超过这个位置
            tmp+=1;
        }
        // 如果这个最小的是第一次出现的，那么更新最小值和记录这个位置即可
        if(mi>tmp){
            mi=tmp
            ans=i+1
        }
    }
    
    return ans;
}