看到题目没有任何头绪,直接查看题解。
至于为什么用二分做呢,讨论区有个友友这么说到:
对于修理时间 t t t 来说:
存在单调性。因此,假设最少需要 t i m e time time 时间,那么我们要找的就是第一个大于等于 t i m e time time 的时间 t t 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;
else
left=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;
else
left=mid+1;
}
return left;
}
时间复杂度:O(
r
a
n
k
s
.
s
i
z
e
(
)
∗
(
log
m
a
x
(
r
a
n
k
∗
c
a
r
s
∗
c
a
r
s
)
)
ranks.size() * (\log max(rank*cars*cars))
ranks.size()∗(logmax(rank∗cars∗cars)) ),每一次二分都要遍历 ranks 数组计算可修理最大车辆数。
空间复杂度:O(1),常数个变量。