５．６ 探索の応用（時間切れ版）

解説そのままやってみて、時間切れのパターン。ここまでは様式美です。ここからバイナリサーチをどう使うのだろう？

現時点でひとつだけ工夫したところは、入力時の最大値を覚えておいて、そこから P を増やしていく部分です。最大値が入らない積載量の探索は意味がないですからね。

#include <iostream>
#include <vector>

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, int P, int k) {
    int i = 0, v = 0;
    for (int 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);
  int P = inputArray(&w[0], n);
  
  for (int v = 0; v < n; P++) {
    v = f(&w[0], n, P, k);
  }

  cout << (P - 1) << endl;

  return 0;
}