D - Allocation

問題

https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/4/ALDS1_4_D (新しいタブで開く)

問題文

重さがそれぞれ $w_i$ の $n$ 個の荷物 $k$ 台のトラックへ。
連続する 0 個以上の荷物を積めるが、最大積載量は $P$ 以下 (全トラック共通)。

$n, k, w_i$ が与えられるので、 $P$ の最小値を出力。

制約

• $1 \le n, k \le 100,000$
• $1 \le w_i \le 10,000$

サンプル

I/O 1

5 3
8
1
7
3
9

10

I/O 2

4 2
1
2
2
6

6

考察

典型的な決め打ちにぶたん。
区間は $\left[ \max w_i, \sum w_i \right] = \left( \max w_i - 1, \sum w_i \right]$ であとはふつうにシミュレーション。

コード

https://onlinejudge.u-aizu.ac.jp/status/users/a01sa01to/submissions/1/ALDS1_4_D/judge/6768367/C++17 (新しいタブで開く)

int main() {
  int n, k;
  cin >> n >> k;
  vector<int> w(n);
  rep(i, n) cin >> w[i];

  int ok = accumulate(w.begin(), w.end(), 0);
  int ng = *max_element(w.begin(), w.end()) - 1;
  while (ok - ng > 1) {
    int mid = (ok + ng) / 2;
    int used = 1, now = 0;
    rep(i, n) {
      if (now + w[i] > mid) {
        used++;
        now = w[i];
      }
      else {
        now += w[i];
      }
    }
    (used <= k ? ok : ng) = mid;
  }
  cout << ok << endl;
  return 0;
}