[每日一题2020.06.17] leetcode周赛T3 5438 制作m束花所需的最少天数二分搜索

题目链接

这题我开始一直在想如何在数组上dp操作搜索区间, 很蠢, 实际上用二分查找的方法可以很快的解决

首先我们通过一个函数判断第x天是否符合题意, 如果x天可以做出m束花, 那么大于m的天数必然可以.

从这里便可以看出其符合二分搜索的特性 :

答案在一个固定区间内；

可能查找一个符合条件的值不是很容易，但是要求能比较容易地判断某个值是否是符合条件的；

可行解对于区间满足一定的单调性。

由于题目设定的最大值是1e9, 我们可以直接把二分的左端设置为0, 右端设置为1e9

判断x天是否满足条件的函数复杂度为$ O(n) $ 而二分查找复杂度为$ O(logn) $ , 故总时间复杂度为$ O(nlogn)$

判断函数 :

bool can(int mid, vector<int>& b, int m, int k) {

	int cnt = 0;

	for (int i = 0; i < b.size(); ++i)

	{

		if(b[i] <= mid)

			cnt++;

		else

			cnt = 0;

		if(cnt==k){

			cnt = 0;

			m--;

		}

		if(m==0)

			return true;

	}

	return false;

}

搜索函数 :

int minDays(vector<int>& bloomDay, int m, int k) {

	if (k*m > bloomDay.size())

		return -1;

	int l = 0;

	int r = 1e9;

	while (l < r) {

	        //int mid = (l + r) >> 1;	这里用下面的方式更安全, 因为这种方式相加可能会溢出 (不是指这道题)

		int mid = l + ((r - l) >> 1);

		if (can(mid, bloomDay, m, k))

			r = mid;

		else

			l = mid + 1;

	}

	return l;

}

巴特西

[每日一题2020.06.17] leetcode周赛T3 5438 制作m束花所需的最少天数二分搜索

最新文章

热门文章

巴特西

[每日一题2020.06.17] leetcode周赛T3 5438 制作m束花所需的最少天数 二分搜索

最新文章

热门文章

[每日一题2020.06.17] leetcode周赛T3 5438 制作m束花所需的最少天数二分搜索