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