一、题目
题目链接
题面
给你一个整数数组 bloomDay,以及两个整数 m 和 k 。
现需要制作 m 束花。制作花束时,需要使用花园中 相邻的 k 朵花 。
花园中有 n 朵花,第 i 朵花会在 bloomDay[i] 时盛开,恰好 可以用于 一束 花中。
请你返回从花园中摘 m 束花需要等待的最少的天数。如果不能摘到 m 束花则返回 -1 。
数据范围
bloomDay.length == n
1 <= n <= 10^5
1 <= bloomDay[i] <= 10^9
1 <= m <=10^6
1 <= k <= n
样例
输入:bloomDay = [1,10,3,10,2], m = 3, k = 1
输出:3
解释:让我们一起观察这三天的花开过程,x表示花开,而 _ 表示花还未开。 现在需要制作 3 束花,每束只需要 1 朵。
1 天后:[x, _, _, _, _] // 只能制作 1 束花
2 天后:[x, _, _, _, x] // 只能制作 2 束花
3 天后:[x, _, x, _, x] // 可以制作 3 束花,答案为 3
输入:bloomDay = [1,10,3,10,2], m = 3, k = 2
输出:-1
解释:要制作 3 束花,每束需要 2 朵花,也就是一共需要 6 朵花。而花园中只有 5 朵花,无法满足制作要求,返回 -1 。
输入:bloomDay = [7,7,7,7,12,7,7], m = 2, k = 3
输出:12
解释:要制作 2 束花,每束需要 3 朵。 花园在 7 天后和 12 天后的情况如下:
7 天后:[x, x, x, x, _, x, x]
可以用前 3 朵盛开的花制作第一束花。但不能使用后 3 朵盛开的花,因为它们不相邻。
12 天后:[x, x, x, x, x, x, x]
显然,我们可以用不同的方式制作两束花。
二、思路
看数据猜算法
n是1e5级别的,也就是 O(n logn) 的算法,又是找需要最小天数的“最优解”,可以想到二分法。
算法实现思路
用二分法寻找最优的天数。显然,假如 i 天能完成,那么 j 天(j>=i)天也能完成。
每次二分天数,需要一个 O(n) 级别的check函数,检查是否能实现。
每次check(day),需要找的是连续的长度==k且bloomDay[i]<=day 的片段,那么可以这样实现。
bool check(int day)
{
int flowers=0,bouquets=0;
for(int i=0;i<num.size();i++)
{
if(num[i]<=day)
{
flowers++;
if(flowers==k)
{
bouquets++;
flowers=0;
}
}
else
{
flowers=0;
}
}
if(bouquets>=m)return 1;
else return 0;
}
读到一个bloomDay[i]<=day,说明这枝花可以用,flowers++;
如果连续一段flowers的长度等于k,那么可以构成一个花束bouquet,bouquets++,flowers归零;
如果读到一个大于day的bloomDay[i],说明前面的flowers已经不能构成一个花束,flowers也归零。
三、代码
- tips:注意ans初值为-1,如果找不到答案就会返回-1。
class Solution
{
vector<int> num;
int tot,len;
bool check(int day)
{
int flowers=0,bouquets=0;
for(int i=0;i<num.size();i++)
{
if(num[i]<=day)
{
flowers++;
if(flowers==len)
{
bouquets++;
flowers=0;
}
}
else
{
flowers=0;
}
}
if(bouquets>=tot)return 1;
else return 0;
}
public:
int minDays(vector<int>& bloomDay, int m, int k)
{
num=bloomDay;
tot=m;
len=k;
int l=0,r=1e9+7,ans=-1;
while(l<=r)
{
int mid=(l+r)/2;
if(check(mid))
{
ans=mid;
r=mid-1;
}
else l=mid+1;
}
return ans;
}
};