The Strict Teacher (Hard Version)

• 思考問題！那么多個人抓一個人，是否是每一個人都是對于最優策略的答案是有貢獻的？
• 答案是否定的，其實問題可以簡化為三種情況：
  • 所有的老師都在大衛的右邊，那么根據最優策略，最快只能是距離大衛最近的老師抓到他
  • 所有的老師都在大衛的左邊，那么根據最優策略，最快也只能是距離大衛最近的老師抓到他
  • 除此之外，大衛被最近的兩個老師包圍，那么根據最優策略，大衛將被這兩個老師抓獲(具體是哪一個老師不重要！)
• 根據上面的三種情況，我們發現首先需要對老師的初始位置進行排序，那么情況就轉化為大衛在不同情況下的活動空間的計算問題
  • 情況1：答案就是b[0]-1
  • 情況2：答案就是n-b[-1]
  • 情況3：答案就是二分得到大衛具體被哪兩個老師包圍，那么就是(b[index]-b[index-1])//2

import bisectt = int(input())for _ in range(t):n,m,q = map(int,input().split())b= list(map(int,input().split()))b.sort()a = list(map(int,input().split()))for i in range(q):if a[i] < b[0]:print(b[0]-1)elif a[i] > b[-1]:print(n-b[-1])else:index = bisect.bisect_left(b,a[i])print((b[index] - b[index-1])//2)