题目：https://leetcode-cn.com/problems/xiao-zhang-shua-ti-ji-hua/

题意：将一个数组分为m份，其中最大个数的那一份元素之和t要最小。

官方题解：如果不考虑每份可以任意减去一个元素，就是一个经典的二分问题，具有单调最优的性质：如果最大值为 t可以满足条件划分，那么最大值为t+1也可以。所以就直接二分最大值t，找到最小满足条件的t即可。本题加了一个条件：每份可以删除任意一个数组。为了能够让最大值最小，显然每份中删去的一定是最大元素，所以在二分判定可行性时，维护当前序列的最大值，然后记录删除最大值的结果，也就是说二分的判定是：是否可以让每组删除最大值之后，总和都小于等于t。

 

理解：

感觉官方的题解看得不是很懂，但二分思想确实是没想到的。其实刚开始对题目的理解有点偏，将问题看成了：求最大解题数且最小使用时间，成了两个目标的问题，感觉实在想不通。但看了官方的解题步骤后，发现其实最大的解题数是不用求解的，我们只要保证在最大的解题数的那天花费的时间最少就行。那么只需要求解t的取值。

可以理解t为在m天中任何一天求解题目最多花费的时间。那么，我们的目标就是，确定一个t值，使该数组中元素之和小于t，且使用天数不大于m。这个t有很多解，要取最小的那一个。

题目中还说了，可以请求一次外援。这点在题解中解释得较清楚，只需要去掉当天解题数目中耗时最多的那题。

class Solution {
    public int minTime(int[] time, int m) {
        int left, right, middle;
        left = right = 0;
        for(int i=0; i<time.length; i++)
            right += time[I];  // right为总的使用时间
        while(left < right){  //开始二分
            middle = (right + left) >> 1;
            if(check(middle, time, m)){
                right = middle;  //t取middle能够在m天内完成解题，那么可行解应该小于等于middle
            }else{
                left = middle + 1;  //t取middle不能在m天完成，那么说明一天的最多解题时间应该再多给点，可行解应该大于middle
            }
        }
        return right;
    }
    /*
    判断一天最多时间limit是否能够让小张在m天内完成
    当 useday<m 时，说明limit能够满足要求
    当 useday>=m 时，说明limit太小了，不足以在m天完成所有题目（注：useday从0开始算）
    */
    private boolean check(int limit, int[] time, int m){
        int useday, maxTime, totalTime;
        useday = totalTime = 0;
        maxTime = time[0];
        for(int i=1; i<time.length; i++){
            int nextTime = Math.min(maxTime, time[i]);  //若当前解题时间time[I]大于最大时间maxTime，那么应该time[i]应该安排外援，所以转而求解maxTime记录的那题
            if(nextTime + totalTime <= limit){  //小于等于limit，当天还能接着解题
                totalTime += nextTime;
                maxTime = Math.max(maxTime, time[i]);  //更新最大解题时间
            }else{  //大于limit，当天不能再花费time[I]时间解题了
                ++ useday;  //天数加1
                totalTime = 0;  //下一天的解题时间从0开始
                maxTime = time[i];  //当前题当作下一天的最大值
            }
        }
        return useday < m;  //看看是不是在规定的时间内完成
    }

    public static void main(String...arg){
        int[] time = {1};
        int m = 2;
//        int[] time = {999, 999, 999};
//        int[] m = 4;
//        int[] time = {1, 2, 7, 4, 7, 7};
//        int m = 2;
        Solution solution = new Solution();
        System.out.println(solution.minTime(time, m));
    }
}