package main

import (
	"fmt"
	"math"
	"sort"
)

// 尝试二分+双指针
func minDays(bloomDay []int, m int, k int) int {
	// 0.特判
	if m * k > len(bloomDay) {
		return  -1
	}
	// 1.map过滤重复的日期
	daySet := make(map[int]int)
	for _ , v := range bloomDay {
		daySet[v] ++
	}
	// 2.map转二分数组
	binaryArr, idx := make([]int, len(daySet), len(daySet)), 0
	for k := range daySet {
		binaryArr[idx] = k
		idx ++
	}
	// 3.对日期数组排序
	sort.Ints(binaryArr)
	// 4.对binaryArr中的日期进行二分搜索,返回符合条件的最小值 , 左闭右闭
	left, right := 0, len(binaryArr) - 1
	minDay := math.MaxInt32
	for left <= right {
		mid := (left + right) / 2
		// 这里写一个方法，判断当天是否满足条件, 如果不满足，增大天数，如果满足，尽量减小天数即可
		ok := canMakeFlower(bloomDay, binaryArr[mid], m, k)
		if !ok {
			// 增大天数
			left = mid + 1
		}else {
			right = mid - 1
			// 尽量减小天数
			minDay = binaryArr[mid]
		}
	}
	return minDay
}

func canMakeFlower(days []int, day int, blocks int, length int) bool {
	left, width := 0, 0
	n := len(days)
	for left < n {
		if days[left] <= day {
			width ++
		}else  {
			width = 0
		}
		if width == length {
			blocks --
			width = 0
		}
		left ++
	}
	return blocks <= 0
}

// 很棒，跟官解几乎一模一样。check方法虽然想了很久，不过最终效果很好，是接近最优的check写法
// 对于指针遍历判断和二分，还是要理清楚逻辑再写，不然容易错误百出
func main() {
	//arr := []int{1,10,3,10,2}
	//m , k := 3, 1

	//arr := []int{7,7,7,7,12,7,7}
	//m , k := 2, 3

	//arr := []int{1000000,1000000}
	//m , k := 1, 1

	//arr := []int{1,10,2,9,3,8,4,7,5,6}
	//m , k := 4, 2

	arr := []int{5,2,2,3}
	m , k := 1 , 1
	fmt.Println(minDays(arr,m,k))
}