GCJ 2017 Qual C. Bathroom Stalls ( Math )

Dashboard - Qualification Round 2017 - Google Code Jam

題意：
有 N 個空間排成一排，有 K 個人依序決定自己要進哪個空間。令一個空間 i 的左邊連續空房間的數量為 L[ i ]，右邊連續空房間的數量為 R[ i ]，那麼任何人都會優先考慮 min( L[ i ], R[ i ] ) 最大的房間，若有多個，便考慮 max( L[ i ], R[ i ] ) 最大的房間，若還是有多個，會選擇 i 最小的房間佔據。問第 K 個人選擇的房間的 R, L 值分別是多少。

制約：
1 ≤ T ≤ 100.
1 ≤ K ≤ N.
1 ≤ N ≤ 1e18.

解法：
這種問題很常見，首先這個問題可以捨去關於下標的資訊，只用空區間長度和對應的數量描述。直覺上可以知道出現的長度種類不會超過 2 * lg N。如果用二元樹擴展的樣子去看，可以發現每層出現的值種類不會超過兩種。因此考慮一層一層擴展，每一層至多兩個元素。

時間 / 空間複雜度：
O( lg N )

from collections import defaultdict
from queue import Queue

T = int( input() )
for ti in range( 1, T + 1, 1 ):
  N, K = map( int, input().split() )
  ans_l, ans_r = -1, -1
  que = Queue()
  que.put( [ N, 1 ] );
  while K > 0:
    cnt = defaultdict( int )
    while K > 0 and not que.empty():
      n, c = que.get()
      K -= c
      ans_l, ans_r = n >> 1, n - 1 >> 1
      cnt[ ans_l ] += c
      cnt[ ans_r ] += c
    for v in sorted( cnt.keys(), reverse = True ):
      if v == 0:
        break
      else:
        que.put( [ v, cnt[ v ] ] )
  print( "Case #%d: %d %d" % ( ti, ans_l, ans_r ) )