2594. 修车的最少时间

题意

• 给定每个师傅修车的时间和需要修的车辆总数，计算修理所有汽车需要的最少时间。
• 师傅可以同时修车。

解法 二分

看到题目没有任何头绪，直接查看题解。

至于为什么用二分做呢，讨论区有个友友这么说到：

对于修理时间 $t$ 来说：

• 若 $t$ 时间内可以修理完所有车，则大于等于 $t$ 时间都可以修理完车；
• 若 $t$时间内不能修理完所有车，则小于等于 $t$ 时间也不能修理完车；

存在单调性。因此，假设最少需要 $time$ 时间，那么我们要找的就是第一个大于等于 $time$ 的时间 $t$ 。

所以可以直接套板子：

class Solution {
public:long long repairCars(vector<int>& ranks, int cars) {long long maxTime = (long long)*max_element(ranks.begin(), ranks.end()) * cars * cars;long long left = 0, right = maxTime, middle;long long maxCar = 0;while(left < right){long long middle = (left +right) / 2;maxCar = 0;for(auto rank :ranks){maxCar += sqrt(middle / rank);  }// cout << left << " " << right << " " << middle << " " << maxCar << endl;if(maxCar < cars){left = middle + 1;}else if(maxCar >= cars){right = middle;}}return left;}
};

另一种写法：

class Solution {
public:long long repairCars(vector<int>& ranks, int cars) {long long maxTime = (long long)*max_element(ranks.begin(), ranks.end()) * cars * cars;long long left = 0, right = maxTime, middle;long long maxCar = 0;while(left <= right){long long middle = (left +right) / 2;maxCar = 0;for(auto rank :ranks){maxCar += sqrt(middle / rank);  }// cout << left << " " << right << " " << middle << " " << maxCar << endl;if(maxCar < cars){left = middle + 1;}else if(maxCar > cars){right = middle - 1;}else if(maxCar == cars){right = middle - 1;}}return left;}
};

板子：

int lower_bound(int a[],int left,int right,int x) 	//第一个小于等于x的数的位置 
{int mid;while(left<right){mid=(left+right)/2;if(a[mid]>=x)right=mid;elseleft=mid+1;}return left;
}int lower_bound(int a[],int left,int right,int x) 	//第一个小于等于x的数的位置 
{int mid;while(left<=right){mid=(left+right)/2;if(a[mid]>=x)right=mid-1;elseleft=mid+1;}return left;
}

复杂度

时间复杂度：O($ranks.size()\ast (\log max(rank\ast cars\ast cars))$ )，每一次二分都要遍历 ranks 数组计算可修理最大车辆数。
空间复杂度：O(1)，常数个变量。

---