【二分】B 019_LC_張刷題計画(欲張り)

一、Problem
n問、番号は0からn-1までで、m日以内に問題番号順にすべての問題を書き上げる計画です(張さんは何日も同じ問題を完成できないことに注意してください).
張さんのブラシ問題計画では、張さんはtime[i]の時間で番号iの問題を完成する必要があります.また、張さんは場外ヘルプ機能を使って、親友の楊さんの問題の解法を聞くことで、この問題の時間を省くことができます.「張さんのブラシ計画」が「楊さんのブラシ計画」になるのを防ぐために、張さんは毎日最大1回助けを求めます.
私たちはm日の中で最も多くの問題を解く時間をTと定義します(楊さんが完成した問題は問題を作る総時間に計上されません).張さんに最小のTがいくらなのかを求めてください.

  ：time = [1,2,3,3], m = 2
  ：3
  ：          ，          ；        ，       。               3    ，         。

制限:
1 <= time.length <= 10^5 1 <= time[i] <= 10000 1 <= m <= 1000
二、Solution
方法一:二分
に言及
time[i]はi i i問題に必要な時間を表し、問題をm日に分けて行うことができ、そのうち1つ1つの問題を捨てることができ、少なくとも何日で問題を完成させることができるかを聞くことができる.
私たちはきっと最も長い問題をしないに違いない.そして、問題をする時間がTを超えたら、新しい日に残りの問題をしなければならない.

class Solution {
    boolean chk(int T, int m, int[] a) {
        int maxT = 0, sum = 0, c = 1;
        for (int t : a) {
            if (sum + t - Math.max(t, maxT) <= T) {
                sum += t;
                maxT = Math.max(maxT, t);
            } else {
                if (++c > m) return false;
                sum = maxT = t;
            }
        }
        return true;
    }
    public int minTime(int[] a, int m) {
        int n = a.length, l = 0, r = (int) 1e9;

        while (l < r) {
            int T = l + r >>> 1;
            if (chk(T, m, a)) r = T;
            else              l = T+1;
        }
        return r;
    }
}

複雑度分析

時間複雑度:O()O(),

空間複雑度:O()O(),