本文涉及知识点

C++贪心
C++二分查找

2616. 最小化数对的最大差值

给你一个下标从 0 开始的整数数组 nums 和一个整数 p 。请你从 nums 中找到 p 个下标对，每个下标对对应数值取差值，你需要使得这 p 个差值的 最大值 最小。同时，你需要确保每个下标在这 p 个下标对中最多出现一次。
对于一个下标对 i 和 j ，这一对的差值为 |nums[i] - nums[j]| ，其中 |x| 表示 x 的 绝对值 。
请你返回 p 个下标对对应数值 最大差值 的 最小值 。
示例 1：
输入：nums = [10,1,2,7,1,3], p = 2
输出：1
解释：第一个下标对选择 1 和 4 ，第二个下标对选择 2 和 5 。
最大差值为 max(|nums[1] - nums[4]|, |nums[2] - nums[5]|) = max(0, 1) = 1 。所以我们返回 1 。
示例 2：
输入：nums = [4,2,1,2], p = 1
输出：0
解释：选择下标 1 和 3 构成下标对。差值为 |2 - 2| = 0 ，这是最大差值的最小值。
提示：
1 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁹
0 <= p <= (nums.length)/2

排序+贪心+二分差值

令选择的第p下标为：i[p]和j[p]，如果nums[i[p]] > nums[j[p]] ，交换之。
kp = nums[i[p]] lp = nums[j[p]]
性质一：不会存在 kp <= kk <= lp。即两组下标不会交叉。
如果：kp <= kk <= lk <= lp ，更换成：kp,kk一组，lk,lp一组更短。
如果 kp <= kk <= lp <= lk，更换成：kp,kk一组，lp,lk一组更短。
性质二：ip+1 = jp，如果不是，更换jp。

二分查找

Check(x): 最大差值是否小于等于x。
pre[0]记录没有选取下标i-1，可以选取的对数。
pre[1]记录选取下标i-1，可以选取的对数。
cur[0] = max(pre[0],pre[1])
如果num[i]-nums[i-1] <= x cur[1] = pre[0]+1。
返回 max(cur[0],cur[1]) >= p ;
pre cur的初始值，全为0。
二分类型：寻找首端。
参数范围（双闭空间）：[0,max(nums)-min(nums)]。

代码

核心代码

template<class INDEX_TYPE>
class CBinarySearch
{
public:
	CBinarySearch(INDEX_TYPE iMinIndex, INDEX_TYPE iMaxIndex):m_iMin(iMinIndex),m_iMax(iMaxIndex) {}
	template<class _Pr>
	INDEX_TYPE FindFrist( _Pr pr)
	{
		auto left = m_iMin - 1;
		auto rightInclue = m_iMax;
		while (rightInclue - left > 1)
		{
			const auto mid = left + (rightInclue - left) / 2;
			if (pr(mid))
			{
				rightInclue = mid;
			}
			else
			{
				left = mid;
			}
		}
		return rightInclue;
	}
	template<class _Pr>
	INDEX_TYPE FindEnd( _Pr pr)
	{
		int leftInclude = m_iMin;
		int right = m_iMax + 1;
		while (right - leftInclude > 1)
		{
			const auto mid = leftInclude + (right - leftInclude) / 2;
			if (pr(mid))
			{
				leftInclude = mid;
			}
			else
			{
				right = mid;
			}
		}
		return leftInclude;
	}
protected:
	const INDEX_TYPE m_iMin, m_iMax;
};

class Solution {
		public:
			int minimizeMax(vector<int>& nums, int p) {
				sort(nums.begin(), nums.end());
				auto Check = [&](int x) {
					vector<int> pre(2);
					for (int i = 1; i < nums.size(); i++) {
						vector<int> cur(2);
						cur[0] = max(pre[0], pre[1]);
						if (nums[i] - nums[i - 1] <= x) {
							cur[1] = pre[0] + 1;
						}
						pre.swap(cur);
					}
					return max(pre[0], pre[1]) >= p;
				};
				CBinarySearch<int> bs(0, nums.back());
				return bs.FindFrist(Check);
			}
		};

单元测试

vector<int> nums;
		int p;
		TEST_METHOD(TestMethod11)
		{
			nums = { 10, 1, 2, 7, 1, 3 }, p = 2;
			auto res = Solution().minimizeMax(nums, p);
			AssertEx(1, res);
		}
		TEST_METHOD(TestMethod12)
		{
			nums = { 4,2,1,2 }, p = 1;
			auto res = Solution().minimizeMax(nums, p);
			AssertEx(0, res);
		}