找出你会得到的马号

Question

我从面试现场测试中得到了这个问题。

有n匹马，而你是排队骑马的kth人。所有排队的人都会选择最低编号的马，即如果第一马和第二马在场的话，该人将选择第一马.All，马有自己的骑行时间，在骑行时间结束后，可供下一轮比赛使用。如果没有马可用，人将等待马的到来，并将继续它。我们得找出我们要骑的马号。

输入：-T。测试用例，不-不。关于马，k-你排队的次数，乘车时间(M)-n个数字，表示马匹的骑行时间。

约束：-1 <= T <= 100，1 <= N <= 1000，1 <= K <= 10^9，1 <= M(i) <= 100000

输出:-你必须告诉马的号码，你将得到。

例如。1

3 8

4 2 1

产出：-1

这里有3匹马，跑时间4，2，1，我排在第8位。所以前三个人将和horse#1，horse#2和horse#3一起去，在这之后就没有马了，所以第四个人必须等待。horse#3是第一位的，所以他会同意的。第五和第六将与horse#2和第六与horse#3，第七将与horse#3和8将与马#1，所以输出是1。

以下是我的代码:-

其时间复杂度为O(N*K)。有没有更好的解决办法。

#include<iostream>
using namespace std;

int main(){

    int t;
    cin>>t;
    while(t--){
        int n,k;
        cin>>n>>k;
        int hrs[n], ans;
        for(int i = 0;i < n;i++)
        cin>>hrs[i];

        if(n >= k){
            cout<<k<<endl;
        }else{
            int tt = 0,p = n;
            int B[n];
            for(int j = 0;j < n;j++)
            B[j] = hrs[j];

            while(p != k){
                tt++;
                for(int m = 0;m < n;m++){
                    if(tt == hrs[m]){
                        p++;
                        hrs[m] += B[m];
                        if(p == k){
                         ans = m;
                         break;
                        }
                    }
                }

            }
            cout<<ans+1<<endl;
        }

      }

    return 0;
}

Answer 1

使用可移植结构

可变长度数组不是标准的C++。使用这样的非标准扩展会阻碍您的代码，因为您无法轻松地使用不同的编译器(这甚至可能排除整个目标平台)。

避免将所有std导入全局命名空间

中。

名称空间为我们提供了一个重要的服务，它将std中的大量且不断增长的标识符与我们自己的代码中的标识符分开。用using namespace std来逆转这种好处是非常有害的。

在读取

时总是测试错误

格式化输入(如std::cin >> n >> k )在使用读取值之前应始终测试流的状态。

使用更清晰的名称

我们不必使用像t这样的名称，因为这正是问题用来描述测试用例数量的原因。类似地，hrs花了我更长的时间来理解horse --这并不会影响你的线路长度。

知道您的标准库

我们有一个优先排队的马，由他们下一次回来的时候，与马的号码作为平局。我们有插入/删除时间为O(log )的std::priority_queue，所以迭代k以前的骑手，找出我们得到的马是O(k log )。

算法非常简单--对于前面队列中的每个成员，从马厩(a std::priority_queue)取下一匹马，将其运行时间添加到下一个可用时间，并将其插入马厩。在马厩前面的马经过k-1迭代后将是我们的。