CFR 806 C. Prairie Partition ( Binary Search, Greedy )
題意:
考慮一種整數的拆分方式,將一個數 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 ) ) )