試圖解決這個任務：
一張自助餐廳餐桌由一排 N 個座位組成，從左到右從 1 到 N 編號。保持社交距離的指導方針要求每位就餐者就座，使左側的 K 個座位和右側的 K 個座位（如果少于 K 個，則該側的所有剩余座位）保持空位。目前有 M 位用餐者坐在餐桌旁，其中第 i 位在座位 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。正確的演算法是什么？
uj5u.com熱心網友回復：
問題在于檢查第一個位置的 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
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/479295.html
上一篇：輸入大小到底是什么