題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 CF83B. Doctor

tags: `二分搜尋(Binary Search)` `模擬(Simulation)`

題意

有 $n$ 個編號 $1$ 到 $n$ 的對象排成一列，每個對象需要被處理 $a_i$ 次。

每次操作時，處理隊伍最前面的對象一次：

如果這個對象還沒被處理完（次數未達 $a_i$ ），就會回到隊伍最後面。
如果已經處理滿 $a_i$ 次，就離開隊伍。
總共會進行 $k$ 次操作。請輸出第 $k$ 次操作結束後，隊伍中剩下的對象編號，按照順序輸出。

如果在第 $k$ 次操作之前，所有對象都已經離開隊伍，輸出 -1。

約束條件

$1 \leq n \leq 10^{5}$
$0 \leq k \leq 10^{14}$
$1 \leq a_i \leq 10^{9}$

思路：二分搜尋

本題的目標是，在操作 $k$ 次後，確定隊伍中剩餘對象的順序。由於 $k$ 可能高達 $10^{14}$ ，若逐次模擬每次看診，效率極低。因此需要優化，可以從總共循環了幾輪來思考。

假設進行了完整的 $m$ 輪，也就是每隻對象最多被處理 $m$ 次。對於第 $i$ 個對象，實際處理次數為 $\min(a_i, m)$ ，其中 $a_i$ 是該對象的需求次數。因此，完成 $m$ 輪後的總處理次數為： $S(m) = \sum_{i=1}^n \min(a_i, m)$

我們希望找到最大的 $m$ ，使得總次數不超過 $k$ ，即滿足 $S(m) \leq k$ ，這可以用二分搜尋來找到。

確定此最大 $m$ 後，剩餘的操作次數（未完成的處理）最多只會少於一整輪，也就是少於 $n$ 次，可以直接模擬即可。

複雜度分析

時間複雜度： $O(n \log M)$
空間複雜度： $O(n)$

from collections import deque

n, k = map(int, input().split())
A = list(map(int, input().split()))

if sum(A) < k:
    exit(print(-1))

# 二分搜尋找到最大完整輪數
def check(m):
    s = sum(min(m, a) for a in A)
    return s <= k

left, right = 0, 10**18
while left <= right:
    mid = (left + right) // 2
    if check(mid):
        left = mid + 1
    else:
        right = mid - 1

# 模擬經過完整 right 輪後的結果
q = deque()
for i in range(n):
    t = min(right, A[i])
    A[i] -= t
    if A[i] > 0:
        q.append(i)
    k -= t

# 直接模擬最後一輪
while k > 0 and q:
    i = q.popleft()
    k -= 1
    A[i] -= 1
    if A[i] > 0:
        q.append(i)

print(*map(lambda x: x + 1, q))

寫在最後

PROMPT

masterpiece, best quality, high quality, highres, extremely detailed CG unity 8k wallpaper, extremely detailed, High Detail, vibrant colors, anime style, cover art,

1girl, solo, Koyori, Hakui Koyori, Hakui Koyori (hololive), pink hair, long hair, braids in hair, purple eyes, fox ears, fox tail, black choker, white short-sleeved blouse, pink bow, pink trim on blouse, pink and purple plaid pleated skirt, white thigh garter on left leg, white knee-high socks, lace-trimmed socks, brown loafers,

reaching up to touch cherry blossoms, sitting on stone wall, spring season, cherry blossom trees in full bloom, soft dreamy lighting, urban background with buildings, gentle breeze, sakura petals falling, peaceful atmosphere, outdoors, clear spring day, looking up with wonder

In this enchanting spring scene, Hakui Koyori sits gracefully on a stone wall beneath a canopy of blooming cherry trees. The soft pink petals create a dreamlike atmosphere around her as she reaches up with one hand to gently touch the blossoms. Her expression captures a moment of serene wonder as she gazes upward at the beautiful sakura, with delicate petals occasionally drifting down in the gentle spring breeze.

新系列？