c++ - 模拟练习的时间复杂度

Question

我遇到了算法复杂性的问题，我尝试了下面的解决方案，但当我忘记考虑时间限制时认为它很容易。我在下面添加了我的代码，我什至不确定其复杂性。我很想知道 O(N) 或 O(K) 解决方案是什么。如果有人可以提供帮助，我们将不胜感激。

Time Limit: 1 second

有 K 个座位可用，每个座位由圆圈周围一点的物理座位表示。 K+1 人最初也站在圆圈周围的点上。圆圈上的点从 1 到 N 顺时针标记，这样点 1 紧跟在点 N 之后。没有两个人最初会站在同一点，也没有两把椅子会在同一点。

每一秒，所有还站着的人(同时)做以下事情:

• If the person is standing at the same point as an empty chair, the person will sit down in it.

• Otherwise, the person will step one place clockwise around the circle to the next point. If the person was previously at point i (with i < N), the person will now be at point i+1. If the person was previously at point N, the person will now be at point 1.

由于有K+1人，最终K个位子都被坐满，剩下的一个人没有位子。坐在圈子里第一个座位的人将拥有最好的位置。 (圆圈中的“第一个”座位定义为从点 1 开始顺时针方向的第一个座位。)

您的任务是确定谁坐在第一个座位上，谁将站着。

输入 N和K。
K 个以空格分隔的整数，按升序表示有椅子的点。因此，此列表中的第一把椅子将是第一把椅子
K+1 个以空格分隔的整数，按递增顺序表示人的点数。这些人根据他们在此列表中的位置从 1 到 K+1 编号。

1≤N≤1000000
1≤K≤100000

输出
坐在第一位的人
人站着

Sample   

Input   
10 3   
2 5 8   
3 4 6 8   

Output   
3   
1   

在第一秒，第四个人(在第 8 点)将立即坐在他们下面的椅子上。其他三人绕圈移动一个位置。下一秒，第二个人(现在是5号位)就会在第二个座位上坐下。第一个人和第三个人继续绕圈走，直到第三个人走到位置2坐下，第一个人就没有椅子可以坐了。

while(standing != 1)
{
    for (int i = 0; i < K + 1; i++)
    {
        if (sitting[i] == 0)
        {
            people[i]++;

            if (isSitting(people[i], chairs,i)) //this function checks if the current person is at a chair
            {
                sitting[i] = 1;
                standing--;
            }

            if (people[i] > N)
            {
                people[i] = 1;
            }
        }
    }

    }
   standingPerson = indexOf(sitting,K+1 ,0);

此尝试在几乎所有测试输入上超时，仅通过 8/30 个案例。

---

下面是一些使用其他用户建议的 O(k) 解决方案的代码。转为c++

    int seat1 = chairs[0], best = -1, accum = 1;
int unlucky[] = {0, -1};

for (int pos; pos < K + 1; pos++) {
    if (people[pos] <= seat1) {
        best = people[pos] + 1;
        accum -= 1;
    } else
        break;
}

if (accum < 0) {
    unlucky[0] = accum;
    unlucky[1] = 1;
}

int i = K, j = K - 1;
while (i >= 0 && people[i] > seat1) {
    if (chairs[j] >= people[i]) {
        accum += 1;
        j -= 1;
    } else {
        accum -= 1;
        i -= 1;
    }
    if (best == -1 && accum == 0) {
        best = i + 2;
    }
    if (accum < unlucky[0]) {
        unlucky[0] = accum;
        unlucky[1] = i + 2;
    }
}
fprintf(out_file, "%d\n%d", best, unlucky[1]);

Answer 1

首先让我们通过将表格视为两个 circular buffers 来简化这个问题。 .一张给椅子，一张给人们。我们可以说缓冲区包含椅子“C”、人“P”和空位“E”。

所以假设我们说循环缓冲区从 1 开始，您的示例可以重写为

E C E E C E E C E E

E E P P E P E P E E

在最坏的情况下，您当前的解决方案是O(N*K)。想象一下这样的配置:

P P E E E E E E E

E E E E E E E E C

您的算法通过将人员缓冲区移动七次来解决上述问题。你通过遍历所有的人并单独改变每个人来实现转变。因此，您的算法进行 O(N)(办公 table 大小)的轮类，每次轮类都涉及将所有 O(K) 人移动一个位置。因此 O(N*K)。不过，我认为这是一个非常悲观的上限，平均而言你会快得多。

---

我认为一个好的 O(K) 可以在两个指针的帮助下实现。一个指向人缓冲区的指针和另一个指向椅子缓冲区的指针。这个想法是分别通过两个缓冲区，并将等待的人与可用的椅子相匹配。这个想法是，每当你看到椅子时，如果有人在等，你就可以将他与那把椅子相匹配。如果没有人在等，则将椅子添加到可用椅子的队列中。如果在我们通过两个缓冲区后有可用的椅子和可用的人，那么我们知道这些人需要通过 table 的 1 点才能找到椅子，我们可以将他们匹配起来通过将最后一个等待的人与第一张可用的椅子相匹配来分配可用的椅子。

除了两个指针之外，您还可以使用两个队列来跟踪可用的椅子和等待的人。以下是该解决方案的伪代码版本。

queue<Person> personQueue;
queue<Chair> chairQueue;
int cptr=0, pptr=0;

while(cptr < K || pptr < K+1) 
    if (cptr >= K) {
        //no chairs ahead of us only behind us
        personQueue.addAllRemainingPersons()
    }
    else if(pptr >= K+1 || chair[cptr] < person[pptr]) {
        // the currently pointed at chair is at a lower position 
        // than the pointed at person,
        // so we match this chair with a waiting person instead
        match(personQueue.back, chair[cptr]);
        cptr++;
    }
    else {
        //add person to the waiting-for-chair queue
        personQueue.push_back(person[pptr]);
        pptr++;
    }
}
// at this point we have a situation with many chair in front of many persons
// for example
// CCCCPPPPP
// This we solve by matching the last person with the first chair 
// until only one is left
while(!cQueue.empty()) {
    match(personQueue.back, chairQueue.front);
}

可以在 match 函数中确定谁坐在第一把椅子上，您有足够的信息可以判断。站着的人是唯一一个没有找到座位的人(唯一一个我们不会称之为匹配的人)。