POJ 1505 Copying Books

問題

要素数mの数列をk個の連続する数列に分割する。分割したそれぞれの数列の要素の和を計算し、そのうち最大となる値を最小化するように数列を分割したい。この条件をみたすように数列を分割して出力せよ。ただし複数の分割方法がある場合には、分割したはじめの数列の和のほうからなるべく小さくなるようにという方針で分割せよ。

やりかた

分割した数列中の和の最大値をXとすると、Xを大きくすると分割数kは小さくなる。なので二分探索で最適な和は計算することができる。
ただしこの問題は頭の方から小さく分割しろという条件が面倒。これには、数列を後ろの方から条件を満たしつつ、貪欲に大きく分割した後、余った分割数分、今度は数列の頭の方から細かく分割していくことで実現できる。

例えば2ケース目の
5 4
100 100 100 100 100
という入力では最小の最大和は200と求まるので、後ろのからひとまず
100 / 100 100 / 100 100
と分割する。分割数が1つ余っているので、今度は頭の方から分割できるところを見つけ次第余った数だけ分割すると答えになる。
100 / 100 / 100 / 100 100

以下ソース。

int m, k;
vector<ll> page;

int C(ll v){
  ll sum = 0;
  int cnt = 0;
  for(int i = m - 1; i >= 0; i--){
    if(v < page[i]) return INF;
    if(sum + page[i] <= v){
      sum += page[i];
    }else{
      cnt++;
      sum = page[i];
    }
  }
  return cnt;
}

int main(int argc, char **argv){
  int n;
  cin >> n;
  while(n--){
    cin >> m >> k;
    page.resize(m);

    ll ub = 0LL, lb = 0LL, div;
    for(int i = 0; i < m; i++){ 
      cin >> page[i];
      ub += page[i];
    }
    
    while(lb < ub){
      ll mid = (ub + lb) / 2;
      div = C(mid);
      if(div + 1 <= k) ub = mid;
      else lb = mid + 1;
    }
    reverse(ALL(page));
    ll sum = 0, rem = k - C(ub) - 1;
    vector<int> a;
    //cout << ub << " " << C(ub) << endl;
    for(int i = 0; i < page.size(); i++){
      if(sum + page[i] > ub){
	sum = 0;
	a.push_back(-1);
      }
      sum += page[i];
      a.push_back(page[i]);
    }
    reverse(ALL(a));
    vector<int> b;
    for(int i = 0; i < a.size(); i++){
      b.push_back(a[i]);
      if(i < a.size() - 1){
	if(rem && (a[i] != -1 && a[i + 1] != -1)){
	  rem--;
	  b.push_back(-1);
	}
      }
    }
    for(int i = 0; i < b.size(); i++)
      if(b[i] == -1) cout << "/ ";
      else cout << b[i] << " ";
    cout << endl;
  }
  return 0;
}