最大値最小問題、二分解答+Javaコード実装

長さnの配列をkセグメントに分割し、各セグメントと最大値の最小値はいくらですか.
問題を解く鍵:まず、解は必ず存在し、最大解は配列のすべての要素の和である.次に,配列を分割した後,各セグメントの和がmを超えず,tセグメントに分割すれば,必ずt−1セグメントに分割できる.だから、kセグメントを超えないように分割できるかどうかを二分して探すだけでいいです.kセグメント以下であれば、必ずkセグメントに拡張できます(いくつかのセグメントを分解するだけでいいからです).
タイトルはYou are given n packages of wi kg from a belt conveyor in order(i=0,1,...n−1).You should load all packages onto k trucks which have the common maximum load PP.Each truck can load consecutive packages(more than or equals to zero)from the belt conveyor unless the total weights of the packages in the sequence does not exceed the maximum load P.Write a program which reads n,k and wi,and reports the minimum value of the maximum load PP to load all packages from the belt conveyor.In the first lineを入力し、two integers n and k are given separated by a space character.In the following n lines,wi are given respectively.出力Print the minimum value of P in a line.サンプル入力5 3 8 8 8 7 3 9サンプル出力10ヒント1≦n≦100000 1≦k≦100000
Javaコード実装

import java.util.LinkedList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        int k = cin.nextInt();
        int[]a = new int[n];
        int left = 0, right = 0;
        for (int i = 0; i < n; i++){
            a[i] = cin.nextInt();
            left = Math.max(left, a[i]);
            right += a[i];
        }
        int mid;
        while(left < right){
            mid = (left + right) >> 1;
//            System.err.println("left="+left+",right="+right+",mid="+mid);
            int t = 1, sum = a[0];
            for(int i = 1; i < n; i++){
                if(sum + a[i] <= mid){
                    sum += a[i];
                }else{
                    t++;
                    if(t > k)break;
                    sum = a[i];
                }
            }
//            System.err.println("t="+t);
            if(t > k){//mid   
                left = mid + 1;
            }else{//mid  
                right = mid;
            }
        }
        System.out.println(right);
    }

}
/*
4 2
1
2
2
6
 */