AOJ0181:Persistence

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0181

方針

本棚の幅で二分探索。
あとはn冊の本を詰めるシミュレートをして、lb/ubを更新していけばよい。
判定は必要な段数のみでなく、本の厚みの最大値 <= 本棚の幅　であることに注意。
計算量はO(n*log(本棚の最大値))だと思う。

以下ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(void){
	int m,n;
	
	while(cin >> m >> n){
		if(!(m|n)) break;
		int lb=0,ub=1500000;
		int maxi = 0;
		vector<int> books(n);
		for(int i=0;i<n;i++){
			cin >> books[i];
			maxi = max(maxi, books[i]);
		}
		while(ub - lb > 1){
			int mid = (lb + ub) / 2;
			int count=1;
			int tmp=0;
			for(int i=0;i<n;i++){
				if(tmp + books[i] <= mid){
					tmp += books[i];
				}else{
					tmp = books[i];
					count++;
				}
			}
			if(count <= m && mid >= maxi){
				ub = mid;
			}else{
				lb = mid;
			}
		}
		cout << ub << endl;
	}
}