题意

小红有n个朋友。她准备邀请一些朋友请他们吃饭。已知第ii个朋友的财富值为ai​，小红邀请他带来的愉悦值为bi​。如果小红邀请的两个朋友的财富值为x和y，那么他们之间就会产生∣x−y∣的隔阂。小红这桌饭局的隔阂值为隔阂最大的那一对朋友的隔阂，这桌饭局的愉悦值为所有受邀朋友的愉悦值总和。小红希望这桌饭局的愉悦值至少达到kk。她想知道最终饭局隔阂的最小值是多少？

思路

隔阂值的定义是隔阂最大的那一对朋友的隔阂，求最后满足xx条件的隔阂的最小值是多少？

这其实可以理解为一个最大值最小化问题，一般推一下单调性的话可以用二分来求。

单调性说明：先按财富值从小到大排序，权值都是正整数，假设现在的饭局是朋友i~j参加，那么多一个朋友的话，愉悦值肯定会增大，而隔阂值也一定会增大；反之同理。

问题转化为check函数：即判断隔阂值最大为mid的时候，愉悦值能否到达k

这里也是比较经典的一个问题，相当于选一段隔阂值<=mid的区间，看愉悦值的最大值。

最朴素的思路就是n^2的暴力，枚举区间长度（通过隔阂值）和区间起点，维护最大值。

但是题意里其实也提到了愉悦值都是正数，贪心地去维护最大值的话，肯定是选择隔阂值尽可能地接近mid的区间，多一个元素对答案的贡献是正数。所以就可以枚举起点，找隔阂值<=mid的最大点，并且O(1)的求这段区间的愉悦值之和。

假设当前枚举的起点是下标i，隔阂值<=mid的最大点实际上就是找小于等于a[i]+mid的最后一个元素，这里又延伸出2种方法：

• 二分找>a[i]+mid的第一个元素，如果这个元素不是最后一个元素的话，让下标减一，就是小于等于a[i]+mid的最后一个元素。
• 直接二分找<=a[i]+mid的最后一个元素，这里最好要判断下如果最后一个元素<=a[i]+mid，直接返回n-1

分别对应下面的代码1和代码2，细节比较多，每个人习惯不一样，可以自行把握。注意点就是如果找不到的话返回最后一个元素的下标

O(1)的求这段区间的愉悦值之和 可以用前缀和维护

这样整体的时间复杂度是O(logn*n*logn)

当枚举区间时，可以通过双指针/滑动窗口减少不必要的状态计算从而降低时间复杂度。比如：如果[1,5]不满足隔阂值的条件，但是[2,5]满足隔阂值的条件的话，那么[1,6]肯定不满足隔阂值的条件，[2,6]可能满足隔阂值的条件，其实[1,6]就不用枚举了。所以对于每一个右端点来说，维护最远的左端点，每次枚举到新的右端点的时候，先将右端点的贡献加入，然后移动左端点使得其称为满足条件的最远的左端点，再维护最大值即可。这样的时间复杂度降到了O(logn*n)

二分套二分代码1

package main

import (
	"fmt"
	"sort"
)

type Friend struct {
	money int
	happy int
}

func main() {
	/*
	   相当于一个最大值最小化问题
	   二分 隔阂的最小值
	   check的时候 判断隔阂值为mid的时候 愉悦值能否到达k
	   二分或是滑动窗口做
	*/
	var n, k int
	fmt.Scan(&n, &k)
	friends := make([]Friend, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&friends[i].money)
	}
	for i := 0; i < n; i++ {
		fmt.Scan(&friends[i].happy)
	}
	//按财富值排序
	sort.Slice(friends, func(i, j int) bool {
		return friends[i].money < friends[j].money
	})
	//fmt.Println(friends)
	l, r, ans := 0, 1_000_000_010, -1
	sum := make([]int, n+2)
	//前缀和
	for i := 0; i < n; i++ {
		if i == 0 {
			sum[i] = friends[i].happy
			continue
		}
		sum[i] = sum[i-1] + friends[i].happy
	}

	find := func(x int) int {
		//找到第一个>x 的元素
		ll, rr, res := 0, n-1, n-1
		for ll <= rr {
			mid := (ll + rr + 1) / 2
			if friends[mid].money > x {
				res = mid
				rr = mid - 1
			} else {
				ll = mid + 1

			}
		}
		return res
	}

	check1 := func(x int) bool {
		//判断隔阂值最大为x的时候 愉悦值能否到达k
		for i := 0; i < n; i++ {
			//找到第一个>a[i].money + x 的元素
			pos := find(friends[i].money + x)
			if pos != n-1 {
				pos--
			}
			//fmt.Println(x, i, friends[i].money+x, pos)
			now := 0
			if i >= 1 {
				now = sum[i-1]
			}
			if pos >= i && sum[pos]-now >= k {
				return true
			}
		}
		return false
	}

	//二分隔阂值
	for l <= r {
		mid := (l + r + 1) / 2
	//	fmt.Println(mid, check1(mid))
		if check1(mid) {
			ans = mid
			r = mid - 1
		} else {
			l = mid + 1
		}
	}

	fmt.Println(ans)
}

二分套二分代码2

package main

import (
	"fmt"
	"sort"
)

type Friend struct {
	money int
	happy int
}

func main() {
	/*
	   相当于一个最大值最小化问题
	   二分 隔阂的最小值
	   check的时候 判断隔阂值为mid的时候 愉悦值能否到达k
	   二分或是滑动窗口做
	*/
	var n, k int
	fmt.Scan(&n, &k)
	friends := make([]Friend, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&friends[i].money)
	}
	for i := 0; i < n; i++ {
		fmt.Scan(&friends[i].happy)
	}
	//按财富值排序
	sort.Slice(friends, func(i, j int) bool {
		return friends[i].money < friends[j].money
	})
	//fmt.Println(friends)
	l, r, ans := 0, 1_000_000_010, -1
	sum := make([]int, n+2)
	//前缀和
	for i := 0; i < n; i++ {
		if i == 0 {
			sum[i] = friends[i].happy
			continue
		}
		sum[i] = sum[i-1] + friends[i].happy
	}

	find := func(x int) int {
        if friends[n-1].money <= x {
            return n-1 
        }
		//找到<=x的最后一个元素
		ll, rr, res := 0, n-1, n-1
		for ll <= rr {
			mid := (ll + rr + 1) / 2
			if friends[mid].money <= x {
				res = mid
				ll = mid + 1
			} else {
				rr = mid - 1

			}
		}
		return res
	}

	check1 := func(x int) bool {
		//判断隔阂值最大为x的时候 愉悦值能否到达k
		for i := 0; i < n; i++ {
			//找到第一个>a[i].money + x 的元素 再减去1
			//最后一个<=a[i].money+x的最后一个元素
			pos := find(friends[i].money + x)
			//fmt.Println(x, i, friends[i].money+x, pos)
			now := 0
			if i >= 1 {
				now = sum[i-1]
			}
			if pos >= i && sum[pos]-now >= k {
				return true
			}
		}
		return false
	}

	//二分隔阂值
	for l <= r {
		mid := (l + r + 1) / 2
		//	fmt.Println(mid, check1(mid))
		if check1(mid) {
			ans = mid
			r = mid - 1
		} else {
			l = mid + 1
		}
	}

	fmt.Println(ans)
}

滑动窗口代码

package main

import (
	"fmt"
	"sort"
)

type Friend struct {
	money int
	happy int
}

func main() {
	/*
	   相当于一个最大值最小化问题
	   二分 隔阂的最小值
	   check的时候 判断隔阂值为mid的时候 愉悦值能否到达k
	   二分或是滑动窗口做
	*/
	var n, k int
	fmt.Scan(&n, &k)
	friends := make([]Friend, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&friends[i].money)
	}
	for i := 0; i < n; i++ {
		fmt.Scan(&friends[i].happy)
	}
	//按财富值排序
	sort.Slice(friends, func(i, j int) bool {
		return friends[i].money < friends[j].money
	})
	//fmt.Println(friends)
	l, r, ans := 0, 1_000_000_010, -1
	check2 := func(x int) bool {
		//判断隔阂值最大为x的时候 愉悦值能否到达k
		//双指针
		ll, rr, now := 0, 0, 0
		for ; rr < n; rr++ {
			//入
			now += friends[rr].happy
			for ll <= rr && friends[rr].money-friends[ll].money > x {
				now -= friends[ll].happy
				ll++
			}
			//判断
			if now >= k {
				return true
			}
  
			
		}
		return false
	}

	//二分隔阂值
	for l <= r {
		mid := (l + r + 1) / 2
		//fmt.Println(mid, check2(mid))
		if check2(mid) {
			ans = mid
			r = mid - 1
		} else {
			l = mid + 1
		}
	}

	fmt.Println(ans)
}