力扣2594.修车的最少时间

题目描述：

给你一个整数数组?ranks?，表示一些机械工的?能力值?。ranksi?是第?i?位机械工的能力值。能力值为?r?的机械工可以在?r * n2?分钟内修好?n?辆车。

同时给你一个整数?cars?，表示总共需要修理的汽车数目。

请你返回修理所有汽车?最少?需要多少时间。

注意：所有机械工可以同时修理汽车。

示例：

示例 1：

输入：ranks = [4,2,3,1], cars = 10
输出：16
解释：
- 第一位机械工修 2 辆车，需要 4 * 2 * 2 = 16 分钟。
- 第二位机械工修 2 辆车，需要 2 * 2 * 2 = 8 分钟。
- 第三位机械工修 2 辆车，需要 3 * 2 * 2 = 12 分钟。
- 第四位机械工修 4 辆车，需要 1 * 4 * 4 = 16 分钟。
16 分钟是修理完所有车需要的最少时间。

示例 2：

输入：ranks = [5,1,8], cars = 6
输出：16
解释：
- 第一位机械工修 1 辆车，需要 5 * 1 * 1 = 5 分钟。
- 第二位机械工修 4 辆车，需要 1 * 4 * 4 = 16 分钟。
- 第三位机械工修 1 辆车，需要 8 * 1 * 1 = 8 分钟。
16 分钟时修理完所有车需要的最少时间。

提示：

• 1 <= ranks.length <= 105
• 1 <= ranks[i] <= 100
• 1 <= cars <= 106

思路：

讲述看到这一题的思路 但凡看到这种求最值方案的题目，应该下意识的去想到用贪心或者动态规划，或者二分去做。这里我想到的是二分。直接二分答案，也就是修车的时间，然后在每一次二分的结果（check(mid)）中去判断，如果这个时候的mid是答案，那么能不能在这个mid时间内修cars辆车呢？换句话来说，在这个时间中我们能修的最大数量的车是多少？由于整个修车队修车的时间取决于最慢（最大）的那一个，其他修车师傅修车的时间<=他，所以这个时候我们假设所有师傅都花了最慢的时间去修车，这样一来，整个修车队的修车时间不变，但是可以修车的总数量却是变多了，这样修车的总数量是当前时间可以修的最大数量！由此，我们在判断整个修车队能不能在当前时间修cars的时候，要用这种贪心的做法去修车，能的话我们放右边，不能的话我们放左边，这样一来，所有可行的方案我们都放在了右边，在所有可行的方案中我们需要找一个答案最小的就是我们要的答案了。

解决方法：

按照以上思路我们需要解决以下问题：

1.找到二分右边界

先遍历数组找到数组最大值max_rank，时间的最大值Tmax=max_rankcarscars.

2.计算每一次二分修车时间的最大修车数量。

按照以上思路，每个修车师傅都花了mid(当前二分的时间)去修车，这样修车的数量是这个时间内最多的，那已经尽力去修车了，修车的数量是多少呢？对于每一位修车师傅，他们修车的时间都是mid,能力值是rank[i]，修车数量就是sqrt(mid/rank[i]),再用个sum加上去就行了，sum为所有修车师傅在修车的数量。

3.在可行方案中找最小方案。 这就是自己二分的思路了，我这里是当sum>=cars时（也就是说当前时间修车队可以修cars数量的车）r=mid，这样一来，最后的可行方案中的最小方案就是r.

代码：

class Solution {
public:
    long long repairCars(vector<int>& ranks, int cars) {
        int mx_rank=0;
        for(int i=0;i<ranks.size();i++){
            mx_rank=max(mx_rank,ranks[i]);
        }
        long long r=(long long )mx_rank*cars*cars+1;
        long long l=0;

        while(l+1!=r){
            long long mid=r+l>>1;
            long long sum=0;//当前时间能修车的最大数量
            for(int i=0;i<ranks.size();i++){
               sum+=sqrt(mid/ranks[i]);
            }
            if(sum>=cars)r=mid;
            else l=mid;
        }

        return r;
    }
};