用社会距离准则定位就餐者的算法

Question

试图解决这个任务：

自助餐厅的桌子由一排N个座位组成，从左到右编号从1到N。社会距离指导原则要求每位就餐者都要坐在左边的K个座位上，右边的K个座位(如果K小于K的话，则其余的座位)保持空。目前有M位就餐者坐在桌旁，第一位在S(i)号座位上。

没有两位就餐者坐在同一个座位上，社会距离的指导原则也得到了满足。确定可能在不违反任何新的或现有食客的社会距离准则的情况下坐在餐桌旁的额外就餐者的最高人数，假设现有的食客不能移动，而且额外的食客将进行合作，最大限度地利用他们中的多少人可以坐下。请注意写一个在时限内运行的解决方案。

Constraints:

1 <= N <= 10^{15} 
1 <= K <=  N
1 <= M <= 500000
M <= N
1 <= S(i) <= N

Sample test case #1
N = 10
K = 1
M = 2
S = [2, 6]
Expected Return Value = 3

Sample test case #2
N = 15
K = 2
M = 3
S = [11, 6, 14]
Expected Return Value = 1

样本解释

在第一种情况下，自助餐厅的餐桌上有N=10座位，目前有两位就餐者分别坐在2号和6号座位上。这张表最初看上去如下，括号覆盖了每一位现有食客的左边和右边的K=1座位，而这些座位可能不会被占用。

  1 2 3 4 5 6 7 8 9 10
  [   ]   [   ]

另外三名就餐者可以坐在4、8和10座位上，而不违反社会距离准则。在第二种情况下，只有1名额外的就餐者能够坐在前3个座位中的任何一个座位上。

我的解决方案适用于两个测试用例(1和2)：

def getMaxAdditionalDinersCount(N: int, K: int, M: int, S: List[int]) -> int:
        
    if N == 0:
        return 0
    
    if K == 0:
        return N
    
    if not S or M == 0:
        return N // (K+1)
    
    pos_cnts = 0   # updated position counts    
    l = sorted(S)  # sort positions in increasing order
   
    first_used_pos = l[0]
    last_used_pos = l[len(l)-1]
    max_pos = N
    tail_len = max_pos - last_used_pos

    # if zero position is not taken yet
    if (1 not in S):
        new_pos_cnt  = first_used_pos // (K+1) - 1
        pos_cnts += new_pos_cnt # update count of all positions
     
    # if last position is not taken yet
    if max_pos not in S:
        new_pos_cnt  = tail_len // (K+1)
        pos_cnts += new_pos_cnt # update count of all positions
    
    indx_prev = l[0]  # index of previous position 
    for indx in l[1:]: # iterate existing positions
        gap = indx - indx_prev
        new_pos_cnt = gap // (K+1) - 1
        pos_cnts += new_pos_cnt # update count of all positions
        indx_prev = indx        
            
    return pos_cnts

然而，对于一个测试用例：

N = 10
K = 1
M = 2
S = [3,5]

它返回错误的答案2而不是3，没有考虑到自由位置1。正确的算法是什么？

Answer 1

问题在检查第一个位置的if条件内：

# if zero position is not taken yet
if (1 not in S):
    new_pos_cnt  = first_used_pos // (K+1) - 1
    pos_cnts += new_pos_cnt # update count of all positions

问题是，当除法中有一个余数时，您必须以不同的方式对待它。您需要修改new_pos_cnt计算，以便在有余数的情况下不会减去一个位置：

# if zero position is not taken yet
if (1 not in S):
    if first_used_pos // (K+1) == first_used_pos / (K+1):
       new_pos_cnt  = first_used_pos // (K+1) - 1
    else:
       new_pos_cnt  = first_used_pos // (K+1) 
    pos_cnts += new_pos_cnt # update count of all positions  

这将为前两个测试用例产生相同的结果，对于第三个测试用例也会产生正确的结果。

For the testcase 1:
first_used_pos = 2
K = 1
first_used_pos // (K+1) -->  2 // (1+1) = 1
first_used_pos /  (K+1) -->  2 /  (1+1) = 1

For the testcase 2:
first_used_pos = 6
K = 2
first_used_pos // (K+1) -->  6 // (2+1) = 2
first_used_pos /  (K+1) -->  6 /  (2+1) = 2

For the testcase 3:
first_used_pos = 3
K = 1
first_used_pos // (K+1) -->  3 // (1+1) = 1
first_used_pos /  (K+1) -->  3 /  (1+1) = 1.5 # Remainder exist -> don't subtract