0w1

GCJ 2017 Qual B. Tidy Numbers ( Ad hoc )

Dashboard - Qualification Round 2017 - Google Code Jam

題意:
問不超過 N 的最大的,以十進制表示時,由左到右檢視,數字呈非遞減的數為何。

制約:
1 ≤ T ≤ 100.
1 ≤ N ≤ 1e18.

解法:
一開始寫數位統計 dp 寫到快哭出來。
仔細想想,只要倒著決定就可以了。
詳細一點,就是由右到左決定,如果遇到衝突,那麼那個衝突發生的左邊的數字 - 1,右邊的數字全部變 9,一定是最好的。只要確保右邊總是盡可能大,左邊一定會有更好的空間發展。至於要 - 1 的數字如果是 0,那麼就要往左找到第一個非零的數字。

時間 / 空間複雜度:
O( log( 10, N ) )

T = int( input() )
for ti in range( 1, T + 1, 1 ):
  N = list( input() )
  ptr = len( N ) - 2
  for i in range( len( N ) - 2, -1, -1 ):
    if ptr < i: continue
    assert( ptr == i )
    if N[ i ] > N[ i + 1 ]:
      while N[ ptr ] == '0':
        ptr -= 1
      N[ ptr ] = chr( ord( N[ ptr ] ) - 1 )
      for j in range( ptr + 1, len( N ), 1 ):
        N[ j ] = '9'
    ptr -= 1
  while len( N ):
    if N[ 0 ] != '0': break
    del N[ 0 ]
  print( "Case #%d: %s" % ( ti, ''.join( N ) ) )