CFR 803 D. Magazine Ad ( Binary Search )

Problem - D - Codeforces

題意：
要求在 K 行以內，用最小的寬度排版文字。輸出最小合理的寬度。一行的末尾必須是空白或是 '-' 符號。保證字不會由 '-' 開頭，也不會有連續的 '-' 或是連續的空白。

制約：
The first line contains number k (1 ≤ k ≤ 1e5).
The second line contains the text of the ad — non-empty space-separated words of lowercase and uppercase Latin letters and hyphens. Total length of the ad don't exceed 1e6 characters.

解法：
二分搜答案，指針亂動就可以了。

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

K = int( input() )
S = list( input().split() )

ans = -1
lb, ub = 1, int( 1e7 )
while lb <= ub:
  mid = lb + ub >> 1
  line, ptr, wptr = 0, 0, 0
  while ptr < len( S ):
    line += 1
    wid = 0
    while ptr < len( S ) and wid + len( S[ ptr ] ) + ( ptr + 1 < len( S ) ) - wptr <= mid:
      wid += len( S[ ptr ] ) + ( ptr + 1 < len( S ) ) - wptr
      ptr, wptr = ptr + 1, 0
    best = wptr # [ wptr, best )
    wnxt = wptr
    while ptr < len( S ) and wnxt < len( S[ ptr ] ) and wid + wnxt + 1 - wptr <= mid:
      if S[ ptr ][ wnxt ] == '-':
        best = wnxt + 1
      wnxt += 1
    wid += best - wptr
    wptr = best
    if ptr < len( S ) and wptr == len( S[ ptr ] ):
      ptr, wptr = ptr + 1, 0
    if wid == 0:
      line = 1 << 30
      break
  if line <= K :
    ans, ub = mid, mid - 1
  else:
    lb = mid + 1
print( ans )