読者です 読者をやめる 読者になる 読者になる

日々精進

aikoと旅行とプログラミングと

【AOJ ALDS1_4】D: Allocation

問題

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

方針

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

コード

#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;
}