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

AOJ0181 Persistence

解法
本が全て「入りきる」または「入りきらない」を評価の条件として、本棚の幅を二分探索により求める。本棚の幅が正の整数の増加列の中の値であることから、この数列のうちで解を仮定して二分探索をすることができる。二分探索の基本問題。

#include <bits/stdc++.h>
using namespace std;

int main() {
  int M, N;
  while(cin >> M >> N && M) {
    vector<int> books(N);
    for(int i=0; i<N; i++) {
      cin >> books[i];
    }
    
    int l = 1, r = 1500001;
    while(r - l > 1) {
      int m = (l+r)/2;
      int bpos = 0;
      for(int i=0; i<M; i++) {
	int size = m;
	for(;;) {
	  if(bpos == N) break;
	  if(size - books[bpos] < 0) break;
	  size -= books[bpos++];
	}
	if(bpos == N) break;
      }
      if(bpos == N) {
	r = m;
      } else l = m;
    }
    
    cout << l+1 << endl;
  }
  
  return 0;
}