package main

import (
	"fmt"
	"sort"
)

// 需要用前缀和+二分优化，甚至还可以继续加上滑动窗口优化,左指针不需要每次都回到右指针的位置
func maxFrequency(nums []int, k int) int {
	res := 1
	n := len(nums)
	if n <= 1 {
		return res
	}
	sort.Ints(nums)
	prefix := make([]int, n+1, n+1)
	for i := 1; i <= n; i++ {
		prefix[i] = prefix[i-1] + nums[i-1]
	}
	// 右指针
	for i := 1; i < n; i++ {
		v := nums[i]
		sort.Search(i, func(x int) bool {
			vSum := v * (i - x + 1)
			nSum := prefix[i+1] - prefix[x]
			if diff := vSum - nSum; diff <= k {
				res = max(res, i-x+1)
				return true
			}
			return false
		})
	}
	return res
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	fmt.Println(maxFrequency([]int{9940, 9995, 9944, 9937, 9941, 9952, 9907, 9952, 9987, 9964, 9940, 9914, 9941, 9933, 9912, 9934, 9980, 9907, 9980, 9944, 9910, 9997}, 7925))
	fmt.Println(maxFrequency([]int{1, 2, 4}, 5))

}