AOJ 0181 - Persistence

はじめての2分探索．

#include<iostream>

const int INF = 1 << 24;
int m, n, a[100];//dansu, honsu
bool C(double x){
	int i = 0, j = 0, l = 0;
	while(i < n && j < m){
		if(l + a[i] <= x){//入る
			l += a[i];
			i++;
		}else{//もう入らない
			l = 0;
			j++;
		}
	}

	if(i == n && j < m)return true;
	return false;
}

int main(){
	while(std::cin >> m >> n, m){
		for(int i=0;i<n;i++){
			std::cin >> a[i];
		}

		int lb = 0, ub = INF;

		for(int i=0;i<100;i++){
			int mid = (lb + ub) / 2;
			if(C(mid))ub = mid;
			else lb = mid;
		}

		std::cout << ub << std::endl;
	}
}