【AOJ ALDS1_4】D: Allocation

問題

割り当て | アルゴリズムとデータ構造 | Aizu Online Judge

方針

• 積載量の最小値を求めたい.
• 0から順にを試し, そのPでk台のトラックを使いすべて積むことができたならそれが答えになる.
• しかし, 順番に調べていくとのアルゴリズムになって終わらなさそう.
• 二分探索を使うととなる.

コード

#include <iostream>

using namespace std;

#define rep(i, n) REP(i,0,n)
#define REP(i,a,n) for(int i = a ; i < (int)n ; i++)

typedef long long ll;

int n, k;
int w[100001];

bool check(int p){
  ll sum=0;
  int idx = 0;

  rep(i, k){
    sum = 0;
    while(w[idx] + sum <= p){
      sum+=w[idx];
      idx++;
      if(idx == n) return true;
    }
  }
  return false;
}

signed main(){
  cin >> n >> k;

  rep(i, n) cin >> w[i];
  
  // binary search
  ll left = 0, right = 100000 * 10000;
  while(right - left > 1){
    ll mid = (left + right) / 2;
    if(check(mid)) right = mid;
    else left = mid;
  }
  
  cout << right << endl;
}