５．６ 探索の応用（バイナリサーチ版）

ということで、バイナリサーチを使う版です。積載量の絞り込みをバイナリサーチで行っていくのですね。数が大きくなると劇的な効果が出ますね。検索回数は log2(1000000000) = 約 30 回でした。

#include <iostream>
#include <vector>

//#include <cstdio>

using namespace std;

static int inputArray(int A[], int num) {
  int max = 0;
  for (int i = 0; i < num; i++) {
    cin >> A[i];
    if (A[i] > max) {
      max = A[i];
    } 
  }
  return max;
}

static inline int f(int A[], int num, uint64_t P, int k) {
    int i = 0, v = 0;
    for (uint64_t total = 0; (v < k) && (i < num); i++) {
      total += A[i];
      if (total > P) {
        total = 0;
        i--;
        v++;
      }
    }
    return i;
}

int main() {
  int n, k;
  cin >> n >> k;

  vector<int> w(n);
  inputArray(&w[0], n);

  uint64_t left = 0;
  uint64_t right = 100000 * 10000;
  uint64_t mid;
  int v = 0;
  while (1 < right - left) {
    mid = (left + right) / 2;
    v = f(&w[0], n, mid, k);
    if (v < n) {
      left = mid;
    } else {
      right = mid;
    }
  }

  cout << right << endl;

  return 0;
}