CFR 795 L. Bars ( Binary Search )

Problem - L - Codeforces

題意：
有 N 天，你有 K 個巧克力棒。第一天和最後一天一定是空的，而且你一定要吃巧克力棒。其他天有些要工作，所以那些天不能吃巧克力棒。問最佳的安排下，你最少的最多不能吃巧克力棒的連續天數。

制約：
The first line contains two integers n and k (2 ≤ n ≤ 200 000, 2 ≤ k ≤ n) — the length of the workday in minutes and the number of chocolate bars, which Polycarp has in the beginning of the workday.
The second line contains the string with length n consisting of zeros and ones. If the i-th symbol in the string equals to zero, Polycarp has no important things to do in the minute i and he can eat a chocolate bar. In the other case, Polycarp is busy in the minute i and can not eat a chocolate bar. It is guaranteed, that the first and the last characters of the string are equal to zero, and Polycarp always eats chocolate bars in these minutes.

解法：
二分搜答案。

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

<?php
  // ( $N, $K ) is not allowed........... claimed by compiler being parsing error
  list($N, $K) = explode(" ", fgets(STDIN));
  $N = (int) $N;
  $K = (int) $K - 2;
  $seq = fgets(STDIN);
  $rp = array(); // rp[ i ] : maximum j such that j ≤ i and seq[ j ] == 0
  for($i = 0, $prev = 0; $i < $N; ++$i) {
    if($seq[$i] == '0') {
      $prev = $i;
    }
    array_push($rp, $prev);
  }
  $lb = 0;
  $ub = $N - 2;
  $ans = $ub;
  while($lb <= $ub) {
    $mid = floor(($lb + $ub) / 2);
    $cost = 0;
    for($i = 1, $prev = 0; $i + 1 < $N; ++$i) {
      $lim = $prev + $mid + 1;
      if($lim >= $N - 1) break;
      if($seq[$i] == '1') {
        if($lim == $i) {
          $cost = $K + 1;
        }
      }
      if($rp[$lim] == $i) {
        ++$cost;
        $prev = $i;
      }
    }
    if($cost <= $K) {
      $ans = $mid;
      $ub = $mid - 1;
    } else {
      $lb = $mid + 1;
    }
  }
  echo $ans;
?>