3

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

Time Limit: 1 second

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

每一秒，所有仍然站立的人（同时）执行以下操作：

  • 如果此人与空椅子站在同一位置，则此人将坐在其中。

  • 否则，该人将围绕圆圈顺时针移动一个位置到下一个点。如果此人之前位于点 i（i < N），则此人现在将位于点 i+1。如果此人先前位于点 N，则此人现在将位于点 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]);
4

2 回答 2

1

首先，让我们通过将表视为两个循环缓冲区来简化这个问题。一张给椅子，一张给人。我们可以说缓冲区包含椅子“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)（桌子的大小）变化，并且每次变化都涉及将所有人移动O(K)一个位置。因此O(N*K)。不过，我认为这是一个非常悲观的上限，平均而言你会快得多。

我认为O(K)可以在两个指针的帮助下实现一个好的。一个指向人员缓冲区的指针和另一个指向椅子缓冲区的指针。这个想法是分别通过两个缓冲区并将等待的人与可用的椅子匹配。这个想法是，每当您看到椅子时，如果有人在等待，那么您可以将他与那张椅子相匹配。如果没有人在等待，则将椅子添加到可用椅子队列中。如果在我们通过两个缓冲区之后有可用的椅子和可用的人，那么我们知道这些人需要通过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);
}

确定谁是坐在第一把椅子上的人可以在匹配功能中进行，您有足够的信息可以分辨。仍然站着的人是唯一没有找到座位的人（唯一一个我们不会称之为匹配的人）。

于 2013-09-19T14:12:17.597 回答
0

为了确定谁将在第一个座位上，我们需要从第一个座位开始反向计算座位/人数，并在人数等于座位数时停止。为了实现这一点，我们需要一个累加器，当遇到座位时增加，遇到人时减少。当这个累加器为零时停止。

为了确定谁是站起来的人，我们可以继续以同样的方式更新累加器，并找到这个累加器第一次获得最小值的位置。对于这个累加器不是最小值的任何人的位置（或者当这个最小值比其他最小值更接近数组的开头时），我们可以在数组后面找到这个累加器具有相同值的位置，这意味着有足够的位置让这个人就座。

有关更详细的说明，请参见下图。它显示所有可能的座位/人员位置的累加器值。虽然算法只遍历输入数组一次，但该图显示了这些数组遍历了 3 次的累加器值，因此问题的循环性质是可见的。

累加器值

每个数组遍历的值彼此相似。唯一的区别是，每次我们到达圆上的同一点时，值都会减一。

很容易注意到，除了一个之外的所有累加器值都具有以下属性：我们总是可以在圆圈中找到另一个具有相同值的点。这意味着这两点之间的座位数和人数相等。这意味着每个起始位置在这两个点之间的人也将坐在这两个点之间的某个位置：右边的所有人都离开这个间隔并且不要假装坐在这些座位上。左边的所有人都来得太晚了。

这些等值点之间的间隔的一些有趣情况是：（1）当间隔跨越数组边界时，（2）两个最小值之间的间隔，（3）当空座位靠近人或他们在同一点。

只有一个位置 (4)，对应于最后一个最小累加器的值（或者如果我们向后搜索，则为第一个）不具有此属性。右边没有相同值的点。处于此初始位置的人将保持站立。

这是 Python 中的工作代码：Ideone 链接。

def solve(k, s, p):
  seat1 = s[0]
  best = -1
  unlucky = (0, -1) # min(accum), position
  accum = 1

  # process all persons between start of the array and the seat #1 position
  for i, pos in enumerate(p):
    if pos <= seat1:
      best = i+1
      accum -= 1
    else:
      break

  if accum < 0:
    unlucky = (accum, 1)

  # process all seats/persons in reverse direction
  i = k
  j = k-1
  while i >= 0 and p[i] > seat1:
    if s[j] >= p[i]: # a seat
      accum += 1
      j -= 1
    else: # a person
      accum -= 1
      i -= 1

    if best == -1 and accum == 0:
      best = i+2 # +1 because indexing starts with 0 & +1 because of pre-decrement

    if accum < unlucky[0]:
      unlucky = (accum, i+2)

  return (best, unlucky[1])


print(solve(3, [2,5,8], [3,4,6,8]))

由于每个座位/人只检查一次，时间复杂度为 O(k)。

于 2013-09-22T13:42:54.780 回答