【算法】白给题（贪心，二分）

偏执的太偏执、 2022-09-16 15:22 161阅读 0赞

**题目描述**  
给定N个自然数，你需要选择M个，使得M个数中两两之间的差的绝对值的最小值尽可能大，求这个最大值。

**输入格式**  
第一行两个空格隔开的正整数N，M，表示自然数个数和要选的数的个数。  
接下来一行为N个空格隔开的给定自然数。

**输出格式**  
一个整数。

**样例输入**  
3 2  
1 2 3  
**样例输出**  
2

## ★解题思路 ##

关键搞清楚什么是“两两之间的差的绝对值的最小值尽可能大”：假设给定一个序列，最小值为10，最大值为90，要求选择两个数，那么显然是选最大值和最小值。  
![在这里插入图片描述][83f269ec682d46ef931083d4df39d634.png]  
如果要求选择3个数，那么应该选择最大数和最小数，以及中间那个数，这里需要考虑一个理论最大间隔的概念：![在这里插入图片描述][683d1ee08c6e4fbeb45dfc1f7c05130b.png]  
所以此时理论上应该选择的数就是50  
![在这里插入图片描述][d629ab161afa42aaacf15413b68ee5ab.png]  
继续，如果要选4个数，也就是要给一个序列分3段，那么有：  
![在这里插入图片描述][1ed35e22370641d9ae232cabcc4ef163.png]  
理论上的一种选择是这样的：  
![在这里插入图片描述][6d0d641cea1b419e9e2fa52e5974ab06.png_x-oss-process_image]  
**具体思路：先计算出理论最大间隔，并进行判断是否符合要求，符合则为答案，不符合则减小最大间隔的长度，继续判断。**

#include <iostream>
    #include <algorithm>
    using namespace std;
    int n,m;
    bool jud(int ans,int a[])
    {
        
    	int index = 0, num = 1;
    	for(int i=1; i<n; i++) {
        
    		if(a[i] >= ans + a[index]) {
        
    			index = i;
    			num++;
    		}
    		if(num >= m) return true;
    	}
    	return false;
    }
    int main()
    {
        
    	scanf("%d %d",&n,&m);
    	int a[n];
    	for(int i=0; i<n; i++) {
        
    		scanf("%d",&a[i]);
    	}
    	sort(a,a+n);//题目没说有序，输入数据当无需处理,故先排序。
    	int ans=(a[n-1]-a[0])/(m-1);
    	while(!jud(ans--,a));//依次减小最大间隔值，直到满足要求 
    	printf("%d\n",ans+1);
    	return 0;
    }

## ★二分改进 ##

最大间隔一个个减少并去判断太慢了，会超时，故应二分。

#include <iostream>
    #include <algorithm>
    using namespace std;
    int n,m;
    bool jud(int ans,int a[])
    {
        
    	int index = 0, num = 1;  
    	for(int i=1; i<n; i++) {
        
    		if(a[i] >= ans + a[index]) {
        
    			index = i;
    			num++;
    		}
    		if(num >= m) return true;
    	}
    	return false;
    }
    int bi(int left,int right,int a[])
    {
        
    	if(left > right) return 0;
    	int mid = left + (right - left)/2; //区间中点，避免溢出式写法 
    	if(jud(mid,a)) {
         //判断当前选取的间隔mid是否满足要求 
    		return max(bi(mid+1,right,a),mid); //向mid偏大的方向二分 
    	} else {
        
    		return bi(left,mid-1,a);//向mid偏小的方向二分 
    	}
    }
    int main()
    {
        
    	scanf("%d %d",&n,&m);
    	int a[n];
    	for(int i=0; i<n; i++) {
        
    		scanf("%d",&a[i]);
    	}
    	sort(a,a+n);
    	printf("%d\n",bi(0,(a[n-1]-a[0])/(m-1),a));
    	return 0;
    }

时间复杂度为O(nlogn)

**二分法举例说明：**

![在这里插入图片描述][f09524327faf4b0e8dfffe8ca977ae06.png]

![在这里插入图片描述][81dadfb63aad4f21b31629d71e6285c1.png]  
![在这里插入图片描述][91e464ff0a0f4731843ef9657bf3bafb.png_x-oss-process_image]  
继续采用二分，选择13不符合要求；选择6不符合要求；选择3符合要求；选择4符合要求；选择5符合要求，并退出二分。  
![在这里插入图片描述][8f9e274a545e4304b150b094899c3a5f.png]

[83f269ec682d46ef931083d4df39d634.png]: /images/20220828/bff71cb2517e4cb0b20d9a1a92d96b8f.png
[683d1ee08c6e4fbeb45dfc1f7c05130b.png]: /images/20220828/9020e7bc7f92490596c0cc4488869cd3.png
[d629ab161afa42aaacf15413b68ee5ab.png]: /images/20220828/076669446d23498caca63543a6e3686c.png
[1ed35e22370641d9ae232cabcc4ef163.png]: /images/20220828/62f8f52cf5d040569b0e68fa36bb3bca.png
[6d0d641cea1b419e9e2fa52e5974ab06.png_x-oss-process_image]: /images/20220828/1cb8545cb4224ec8994c48d6573de3b4.png
[f09524327faf4b0e8dfffe8ca977ae06.png]: /images/20220828/b76ec87d25b44762b21685e959247eac.png
[81dadfb63aad4f21b31629d71e6285c1.png]: /images/20220828/e8eb1e03aa70497583bb8a1dd28bd3ec.png
[91e464ff0a0f4731843ef9657bf3bafb.png_x-oss-process_image]: /images/20220828/92ca116912654ce0a1448934d3bb679d.png
[8f9e274a545e4304b150b094899c3a5f.png]: /images/20220828/fbdb3f87f2aa4cccacce912167842fa8.png