Subscribed unsubscribe Subscribe Subscribe

0w1

CFR 806 C. Prairie Partition ( Binary Search, Greedy )

Problem - C - Codeforces

題意:
考慮一種整數的拆分方式,將一個數 x 拆分為 x = 1 + 2 + 4 + .. + 2^( k - 1 ) + r, 1 ≤ k and 0 ≤ r ≤ 2^k。原本有若干個數,進行這樣的拆分後,排序好,現在給你。問所有可能的原序列長度。

制約:
The first line contains a single integer n (1 ≤ n ≤ 1e5) — the number of numbers given from Alice to Borys.
The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 1e12; a1 ≤ a2 ≤ ... ≤ an) — the numbers given from Alice to Borys.

解法:
令 1 的數量為 k。很容易發現,如果長度為 k 是做不到的,那麼未滿 k 的所有長度一定也都是做不到的。
反之,如果一個隨意的長度 x 是做得到的,那麼所有介於 [ x, k ] 的長度都是做得到的。
因此考慮二分搜,找出最小的可行長度。
至於如何檢驗一個長度是否可行,考慮使用貪心策略。
考慮定義「累贅」,顯然的累贅是非 2 的冪次的所有值。
這些累贅必須要一對一對應一個 r = 0 的拆分,另一個累贅為 v,那麼令 t 為最大的 t 滿足 2^t < v,則 v 對應的拆分的長度必須是 t 以上的。
考慮由小到大枚舉二的冪次,一面維護當前還沒有斷的可對應拆分數量。如果當前這個二的冪次的數量多於可對應數量,那麼這個強度的累贅就要增加多的數量,否則若二的冪次的數量少於可對應數量,那麼可對應數量應降到二的冪次的數量,不見的就算是結束增長了。最後可以生成出屬於尾巴的二的冪次的強度們,以及累贅的強度們。若且唯若前者的數量不少於後者的數量,且存在一種一對一對應,使得前者都不小於後者,就是可行的。

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

from functools import reduce

N = int( input() )
A = list( map( int, input().split() ) )

cntp2 = [ 0 for i in range( 50 ) ]
zanp2 = [ 0 for i in range( 50 ) ]

for i in range( N ):
  t = max( list( filter( lambda x: A[ i ] >> x & 1, range( 50 ) ) ) )
  if 1 << t == A[ i ]:
    cntp2[ t ] += 1
  else:
    zanp2[ t ] += 1

def ok( gol_len ):
  c = [ v for v in cntp2 ]
  z = [ v for v in zanp2 ]
  for i in range( 50 ):
    if c[ i ] <= gol_len:
      gol_len = c[ i ]
    else:
      z[ i ] += c[ i ] - gol_len
      c[ i ] = gol_len
  sc = reduce( list.__add__, ( list( j for i in range( c[ j ] - c[ j + 1 ] ) ) for j in range( 50 - 1 ) ) )
  sz = reduce( list.__add__, ( list( j for i in range( z[ j ] ) ) for j in range( 50 - 1 ) ) )
  return len( sc ) >= len( sz ) and all( sc[ i + len( sc ) - len( sz ) ] >= sz[ i ] for i in range( len( sz ) ) )

if not ok( cntp2[ 0 ] ):
  exit( print( -1 ) )

lb, ub = 0, cntp2[ 0 ] # ( lb, ub ]
while lb + 1 < ub:
  mid = lb + ub >> 1
  if ok( mid ):
    ub = mid
  else:
    lb = mid
print( ' '.join( str( i ) for i in range( ub, cntp2[ 0 ] + 1 ) ) )