leetcode 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^5
• 0 <= nums[i] <= 10^9
• 0 <= p <= (nums.length)/2

分析：二分答案，左端点为 0，右端点为数组元素的最大值，检查能否找到 p 个差值小于等于 mx 的数对。先对数组进行排序，之后相邻元素的差如果小于 mx，就计算一次差值，循环下标右移 2 位，否则循环下标右移 1 位。

检查满足差值小于等于 mx 的数对个数。贪心进行选择，从左到右遍历时，只要 nums[i] 与 nums[i+1] 构成的数对满足条件就立刻选取。假设不选 nums[i]，从剩下的数中能够选出的对数一定不会超过选 nums[i] 时的对数，所以贪心策略是正确的。

int cmp(const void *a,const void *b)
{
    int *aa=(int*)a;
    int *bb=(int*)b;
    return (*aa)-(*bb);
}

int minimizeMax(int* nums, int numsSize, int p) {
    if(!p)return 0;
    qsort(nums,numsSize,sizeof(int),cmp);

    // for(int i=0;i<numsSize;++i)
    //     printf("%d ",nums[i]);

    int ans=0,l=0,r=nums[numsSize-1],mid;
    while(l<=r)
    {
        // printf("l=%d r=%d\n",l,r);
        int mid=(l+r)/2,cnt=0;
        for(int i=1;i<numsSize;)
        {
            int sum=nums[i]-nums[i-1];
            if(sum<=mid)cnt++,i+=2;
            else i++;
        }
        if(cnt>=p)ans=mid,r=mid-1;
        else l=mid+1;

        // printf("l=%d r=%d cnt=%d p=%d mid=%d ans=%d\n",l,r,cnt,p,mid,ans);
    }

    return ans;
}