Subscribed unsubscribe Subscribe Subscribe

0w1

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;
?>