首页 > 试题广场 >

牛牛排队

[编程题]牛牛排队
  • 热度指数：1511 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
下课了，牛牛要去食堂吃饭，他们学校的食堂有很多个门，而且整个建筑物是圆形的。只不过要去吃饭的人很多，在里面吃饭的人也很多，所以大家都在门口外面排队等待吃饭。
所以牛牛采取了这样的一个策略：刚开始时，牛牛在第一个门口，如果这个门口有人在排队，那么他选择花费1分钟时间走到下一个门口，如果没有人的话，牛牛就可以直接进去吃饭啦。食堂的每一个门，每1分钟排队的人数都会减少一个。
现在给你门的数量n，和每个门外排队的人的数量，如果按照牛牛的策略，那么牛牛最终会在哪个门进去吃饭呢？请你进行编程求解，返回牛牛最终是从第几个门进入食堂吃饭的。
示例1

输入

4,[2,3,2,0]

输出

3

说明

按照牛牛的策略，每个门口外的排队人数随着时间的变化的结果为[2,3,2,0]→[1,2,1,0]→[0,1,0,0]，当牛牛走到第3个门时，刚好没有人排队，所以牛牛最后可以从第3个门进去。
示例2

输入

2,[10,10]

输出

1

说明

按照牛牛的策略，每个门口外的排队人数随着时间的变化的结果为[10,10]→[9,9]→[8,8]→[7,7]→[6,6]→[5,5]→[4,4]→[3,3]→[2,2]→[1,1]→[0,0]
，当牛牛走到第五圈，回到第1个门时，刚好没有人排队，所以牛牛最后可以从第1个门进去。

备注:





算法知识视频讲解
添加回答
Python 3
ZhongHaoWang头像 ZhongHaoWang 
class Solution:
    def nowcoderQueue(self , n , a ):
        # write code here
        cnt = []
        for i in range(len(a)):
            cnt.append((a[i] - i) // n if (a[i] - i) % n == 0 else (a[i] - i) // n + 1)
        cur_l = float('inf')

        ans = -1
        for i in range(len(cnt)):
            if cnt[i] < cur_l:
                cur_l = cnt[i]
                ans = i + 1
        return ans

发表于 2021-08-27 12:55:04 回复(0)
全旋的托马斯头像 全旋的托马斯
就有个小问题啊：建筑物不是圆形的么？题里面那个例子直接反着一转不就从最后一个门进去了么。。。
发表于 2021-07-20 23:09:45 回复(0)
Python
袁博文202头像 袁博文202
有些测试样例，a[i]值过大，导致循环次数过大，运行时间过长。需要在循环前，整体降低数组的数值，进行加速。
python3代码 
class Solution:
    def nowcoderQueue(self , n , a ):
        # write code here
        door = 0
        t = 0
        minp = min(a) // n * n
        for i in range(n):
            a[i] = a[i] - minp
        while True:
            if a[door] > t:
                door = (door + 1) % n
                t += 1
            else:
                return door + 1


发表于 2021-07-06 10:29:13 回复(0)
坚持就是yes头像 坚持就是yes
我写这题的思路:
思路一：
    刚开始这样想的，用index记录当前的数组下标，走一个窗口，使得每个窗口的人数自减一，最后遍历到当前位置如果是0，则结束。但是很不幸，超时了，毕竟每次都去将所有的窗口人数自减一，还是很麻烦的。改进如下 
public int nowcoderQueue (int n, int[] a) {
        // write code here
        boolean flag =true;
        int index=0;
        while(flag){
            if(a[index%a.length]==0){
                flag = false;
            }else{
                index++;
                for(int i=0;i<a.length;i++){
                    if(a[i]>0){
                        a[i]--;
                    }
                }
            }
        }
        return index%a.length+1;
    }
思路二：
    上面的问题出在自减一，那我就用一个int count变量来记录牛牛走了几步，然后只需要遍历到的窗口减去这个count值就代表着这个窗口还剩几个人了。代码如下.但是很不幸，又超时了，最后一个用例通不过 2,[999999999,1000000000]，想了想，这样确实挺费时的，多转了很多个来回，可不可以不然他这么来回转呢？改进如下 
public int nowcoderQueue (int n, int[] a) {
        // write code here
        boolean flag =true;
        int index=0;
        int count=0;
        while(flag){
            if((a[index%a.length]-count)<=0){
                flag = false;
            }else{
                index++;
                count++;
            }
        }
        return index%a.length+1;
    }
思路三：我们一次遍历完可以找出数组中的最小值吧，min，如果这个min值小于数组的长度，那么说明我们只要再遍历一遍（最多两遍）就必定可以找出空窗口。如果这个min值大于数组的长度，说明我们下一次遍历还是找不到结果，意味着我们将白白遍历一遍，那么我们怎么样才能不走这一趟冤枉路呢？ 我们可以对这个min值对数组长度整除 得到int temp = min/a.length，然后对计数值count做改动 count=count+a.length*temp;这样接下来的遍历就很容易找到空窗口了。代码如下：
public int nowcoderQueue (int n, int[] a) {
        // write code here
        boolean flag =true;
        int index=0;
        int count=0;
        int min=a[0];
        while(flag){
            if((a[index%a.length]-count)<=0){
                flag = false;
                break;
            }else{
                if((a[index%a.length]-count)<min){
                    min=a[index%a.length]-count;
                }
                index++;
                count++;
            }
                        //表示一次遍历到头，处理下最小值min
                if(min>a.length){
                    int temp = min/a.length;
                    count=count+a.length*temp;
                }
            }
        }
        return index%a.length+1;
    }
有需要改进的地方请大家不吝指出。感谢！



编辑于 2021-07-02 15:29:48 回复(0)
boumbo头像 boumbo
1、思路求出假如需要走每个门所需要等待的时间，最后求出最短的等待时间的那个门就行了
2、这里需要注意的就是排完当前队的人自已的位置是在哪，分两种情况一个是在当前计算门的左边。一种是在当前计算门的右边，右边相当于需要绕一圈回来。 
class Solution:
    def nowcoderQueue(self, n, a):
        # write code here
        # 求出每个门轮到的次数，取最小的那个

        if a[0] == 0:
            return 1
        min_count = 9999999999999999999
        index = 0
        for i, j in enumerate(a):
            # 如果要到当前门需要多少时间
            gate_index = j % n
            # 如果gate_index小于i,则不用绕一圈
            if gate_index < i:
                count = j + i - gate_index
            elif gate_index > i:
                # 如果gate_index大于i，则相当于走到队尾再回来
                count = j + n - gate_index + i
            elif gate_index == i:
                count = j

            if count < min_count:
                index = i
                min_count = count

        return index + 1


发表于 2021-05-11 14:41:04 回复(0)
花落梦里头像 花落梦里 
    public int nowcoderQueue (int n, int[] a) {
        int time=0;//已经过去的分钟数
        while(true){
          for(int i=0;i<n;i++){
            if(a[i]-time<=0) return i+1;
            time++;
          }
        }
    }

发表于 2021-03-31 16:27:06 回复(0)
C/C++
梁石页头像 梁石页
请问为什么我用int Ans=0就只通过90%测试用例，显示运行超时，循环过多。
而用int Ans = *min_element(a.begin(),a.end())/n*n;初始值也是0就可以通过所有用例呢？
int nowcoderQueue(int n, vector<int>& a) {
        //int Ans = 0;
        int Ans = *min_element(a.begin(),a.end())/n*n;
        while(Ans < a[Ans++ % n]);
        return (Ans - 1) % n + 1;
    }
发表于 2021-02-10 10:47:58 回复(1)
提交观点

问题信息

数组 思维
难度：
7条回答 2805浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号