3273-Monthly Expense

問題（外部リンク）

3273 -- Monthly Expense

実装の概要

1期間あたりの予算の下限を求める問題です。解を仮定して二分探索で絞り込む方法で解きます。蟻本では「最小値の最大化」として紹介されていますが、実際には「最大値の最小化」なので絞り込みの部分などは適宜書き換える必要があります。
判定法についてですが、「1期間あたりの予算をlimitとした上で、期間をm以下にできるか」とします。mとちょうど等しくなる必要はありません。期間が余ったなら適当なところを分割しても構わないからです。
これについてはループを回して「合計金額がオーバーしたら期間が切り替わる」と考えれば1回あたりで判定できます。なお、1日だけでオーバーする場合は論外なのでその時点でfalseを返します（そうならないようにleftをmoneyの最大値-1などにするのもありかもしれません）

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String tmpArray[] = br.readLine().split(" ");

		int n = Integer.parseInt(tmpArray[0]);
		int m = Integer.parseInt(tmpArray[1]);

		int money[] = new int[n];

		for(int i = 0; i < n; i++){
			money[i] = Integer.parseInt(br.readLine());
		}

		System.out.println(solve(money, m));
	}

	static int solve(int money[], int m){
		int n = money.length;

		int left = 0;
		int right = 10000*100000 + 1;

		//解を仮定して二分探索
		while(right - left > 1){
			int mid = (left + right)/2;

			if(check(money, m, mid)){
				right = mid;
			}
			else {
				left = mid;
			}
		}

		return right;
	}

	//毎月limit以内の出費に収めることができるか
	static boolean check(int money[], int m, int limit){
		int n = money.length;

		int tmpSum = 0;
		for(int i = 0; i < n; i++){
			//1日だけでオーバーする場合は不可
			if(money[i] > limit){
				return false;
			}
			//i日目を加えても予算に収まる場合
			if(tmpSum + money[i] <= limit){
				tmpSum += money[i];
			}
			//予算オーバー
			else {
				m--;
				if(m <= 0){
					return false;
				}
				tmpSum = money[i];
			}
		}
		return true;
	}
}