当前位置:   article > 正文

刷题日志(5)——二分答案法

刷题日志(5)——二分答案法


一. 二分答案法

1. 估计最终答案的可能范围 (该范围可以定的很宽,即没有必要一定是精确的范围!!!)
2. 分析 问题答案与 给定条件的单调性。
3. 建立函数F,在答案固定的情况下,判断答案是否达标。
4. 在答案的可能范围上不断二分,每次使用F函数判断,直到二分解结束,找到适合的答案

关键: 分析单调性,建立F函数

二、爱吃香蕉的珂珂

在这里插入图片描述
分析:
1.由题知,要想总时间最少,则吃香蕉的速度一定要最快,但由于吃掉一份后必须等等,因此速度k>=max(nums[i])即可。故答案的范围在1——max(nums[i])
2.显然,当吃香蕉的速度逐渐增大时,其花费的时间一定是不变或者减少,即存在单调性
3.设置F函数功能:判断速度k是否能够达标

//F函数:用于判断是否达标
//本题可以使用位运算来优化F函数中向上取整的方法
int judge(int* nums,int numsSize,int h,int speed)
{
    int ans=0;
    for(int i=0;i<numsSize;i++)
    {
        if(nums[i]%speed!=0)
        {
            ans+=nums[i]/speed+1;
        }
        else
        {
            ans+=nums[i]/speed;
        }
    }
    return ans>h?0:1;
}
//获取数组最大值
int getmax(int* nums,int numsSize)
{
    int Max=-1;
    for(int i=0;i<numsSize;i++)
    {
        if(nums[i]>Max)
            Max=nums[i];
    }
    return Max;
}
int minEatingSpeed(int* piles, int pilesSize, int h) {
    int l=1;
    int r=getmax(piles,pilesSize);  //l,r为答案区间,
    int ans=0;
    while(l<=r)
    {  
        int mid=l+(r-l)/2;   //不断对答案进行二分查找
        if(judge(piles,pilesSize,h,mid)==0)  
        {
            l=mid+1;    //说明该时间不达标,因此区间修改为[mid+1,r]
        }
        else
        {
            r=mid-1; 
            ans=mid;  //达标则记录结果,并修改区间为[l,mid-1]来寻找更优的结果。
        }
    }
    return ans;
}
//时间复杂度:O(n*logm) ,n为数组长度,m为数组最大值    空间复杂度:O(1)
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49

三. 分割数组的最大值 (画匠问题)

在这里插入图片描述
分析:
首先,根据题意得到,ans=max(每部分子数组累加和),因此需要解决的是在k的划分下,子数组和应尽可能小,这显然很符合二分答案的特征。
1.由题知,答案显然可以确定范围,为0——sum(nums[i])(即整个数组作为一次划分,虽然该范围很粗糙,但是
二分答案的范围时间并不需要严格给出!!!

2.存在单调性,即当max(子数组累加和)不断增大时,则划分出来的子数组数量会越来越少或者不变。
3.F函数功能:给定一累加和,判断需要的划分数与k的关系

//在累加和为limit情况下,对数组进行划分,判断其划分数量是否<=k
//实现:遍历数组,判断sum+nums[i]与limit关系
//如果前者大,则认为这是一次划分,sum重新从nums[i]开始
//如果后者大,则该子数组依然可以存放元素,则sum+=nums[i]
//如此往复直至遍历完成,如果完成后的划分数量>k,则说明不符题意
//否则,则认为该划分有效
int judge(int* nums,int numsSize,long limit,int k)
{
    int parts=1;  //第一个划分开始
    long sum=0;
    for(int i=0;i<numsSize;i++)
    {
        if(nums[i]>limit)  //如果数组元素大于limit,则一定无法划分
        {
            return 1;
        }
        if(sum+nums[i]>limit)
        {
            sum=nums[i];
            parts++;       //当一个区间划分完成后,开始下一个区间的划分
        }
        else
        {
            sum+=nums[i];
        }
    }
    return parts>k?1:0;
}
int splitArray(int* nums, int numsSize, int k){
    long sum=0;
    for(int i=0;i<numsSize;i++)
    {
        sum+=nums[i];
    }
    long l=0;
    long r=sum;      //二分区间
    long ans=0;
    while(l<=r)
    {
        long mid=l+(r-l)/2;
        if(judge(nums,numsSize,mid,k)==0)
        {
            r=mid-1;
            ans=mid;
        }
        else
        {
            l=mid+1;
        }
    }
    return (int)ans;
}
//时间复杂度O(n * log(sum)),额外空间复杂度O(1)
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53

四. 机器人跳跃问题

在这里插入图片描述
分析:

  1. 可以确定答案范围,即能量范围为0——max(nums[i])
  2. 显然存在单调性,即能量越小越不容易通过,而能量越大,越容易通过
  3. F函数功能:判断该能量是否可以通关
#include <stdio.h>
#include <limits.h>
#include <stdlib.h>
//获取数组最大值
int getmax(int* nums,int numsSize)
{
    int max=INT_MIN;
    for(int i=0;i<numsSize;i++)
    {
        if(max<nums[i])
        {
            max=nums[i];
        }
    }
    return max;
}
//F函数:判断是否可以完成任务
int judge(int* nums,int numsSize,long long value,int max)
{
    int flag=0;
    for(int i=0;i<numsSize;i++)
    {
        if(nums[i]-value>=0)
        {
            value-=nums[i]-value;
        }
        else
        {
            value+=value-nums[i];
        }
        if(value>=max)      //一定需要判断,否则若能量很大,则很可能超过long类型的大小
        {
            break;
        }
        if(value<0)
        {
            flag=1;  //无法完成
            break;
        }
    }
    return flag;
}
int minEngine(int* nums,int numsSize)
{
    int l=0;
    int ans=0;
    int r=getmax(nums,numsSize);       //通过所需能量范围[l,r]
    while(l<=r)
    {
        int mid=l+(r-l)/2;   //给定能量
        if(judge(nums,numsSize,(long long)mid,getmax(nums,numsSize))==0)             
        {
            r=mid-1;
            ans=mid;       //可以完成,记录结果,答案区间缩小为[l,mid-1]
        }
        else
        {
            l=mid+1;      //该能量无法完成,区间更新为[mid+1,r]
        }
    }
    return ans;
}
int main() {
    int N=0;
    while (scanf("%d\n", &N) != EOF)
    {
        // 注意 while 处理多个 case
        int* nums=malloc(sizeof(int)*N);
        for(int i=0;i<N;i++)
        {
            scanf("%d",&nums[i]);        
        }
        printf("%d\n", minEngine(nums,N));
    }
    return 0;
}
//时间复杂度:O(n*logmax)      空间复杂度:O(1)
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77

五. 找出第k小的数对距离

在这里插入图片描述
分析:
1.显然,可以确定答案数对距离的范围,即0——max(nums[i])-min(nums[i])
2.显然存在单调性,数对距离越大,其找到的数对就越多
3.F函数:在给定数对距离的情况下,计算该距离下有多少对数对
4.比较F返回结果与k的关系,不断二分,直至找到结果。

//归并排序
void merge(int* arr, int left,int right,int* tmp)
{
    if (left >= right)
        return;    
    int i = 0;
    int mid = left + ((right - left) >> 1);   //中点
    merge(arr, left, mid, tmp);
    merge(arr, mid + 1, right, tmp);    
    int p1 = left;
    int p2 = mid + 1;
    while (p1 <= mid && p2 <= right)
    {
        if (arr[p1] <= arr[p2])
        {
            tmp[i++] = arr[p1++];
        }
        else
        {
            tmp[i++] = arr[p2++];
        }
    }
    while (p1 <= mid)
    {
        tmp[i++] = arr[p1++];
    }
    while (p2 <= right)
    {
        tmp[i++] = arr[p2++];
    }
    for (int j = 0; j < (right-left)+1; j++)
    {
        arr[left + j] = tmp[j];
    }
}
void Mergesort(int* arr, int n)
{
    int* tmp = (int*)malloc((n) * sizeof(int));
    merge(arr, 0, n - 1, tmp);
    tmp = NULL;
    free(tmp);
}

int f(int* nums,int numsSize,int limit)
{
   int ans = 0;
   for (int l = 0, r = 0; l < numsSize; l++)
   {
		// l......r r+1,始终维护窗口
        //每次对r+1位置判断,因此需要保证遍历范围
	    while (r + 1 < numsSize && nums[r + 1] - nums[l] <= limit) 
        {
			r++;     //如果符合条件,则将窗口扩大
		}
		// arr[l...r]范围上的数差值的绝对值都不超过limit
		// arr[0...3]
		// 0,1
		// 0,2
		// 0,3
		ans += r - l;   //每次ans加上以l开头的数对数目
	}
    return ans;
}
int smallestDistancePair(int* nums, int numsSize, int k) {
    int l=0;
    int ans=0;
    int cnt=0; 
    Mergesort(nums,numsSize);
    int r=nums[numsSize-1]-nums[0];
    while(l<=r)
    {
        int mid=l+(r-l)/2;
        cnt=f(nums,numsSize,mid);
        if(cnt>=k)
        {
            ans=mid;
            r=mid-1;
        }
        else
        {
            l=mid+1;
        }   
    }
    return ans;
}
// 时间复杂度O(n * log(n) + log(max-min) * n),额外空间复杂度O(1)
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86

六. 总结

二分答案法通常用于解决优化问题,其中答案满足某种性质,并且存在一个可以比较的函数(通常称为检查函数),通过调整答案来满足或最大化/最小化这个性质。当使用条件满足时,二分答案法会是一种非常高效的方法。
使用二分答案时,尤其要注意变量的范围,如果不能正确的定义适当大小的变量,其最终很可能导致出错。典型的是当数组长度非常长时,如果最终ans为0,那么很可能是变量类型定义的有问题,ans类型,F函数中的变量类型均有可能!!!

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/IT小白/article/detail/645436
推荐阅读
相关标签
  

闽ICP备14008679号