基础算法模板

  1. 尺取法模板

  2. void solve(){
        int L=1,R=1;//两个指针
        int sum=0;//区间和
        int now=0;//当前方案
        int minn=INF;
        while(R<=N){
    
            while(sum<S&&R<=N){//R总指向当前满足要求区间的下一个,此处R可能>N 
                sum+=a[R];//累加器加上右指针指向的元素
                ++R;//右指针向右移
                ++now;
            }
    
            while(sum>=S){//L总指向当前区间的最左边,左闭右开 
                sum-=a[L];//累加器减去左指针指向的元素的值
                ++L;//左指针右移
                --now;
            }
    
            minn=min(minn,now+1);//更新最优方案
        }
    }

    二分法模板

    //x:待查找的元素, n:数组集合大小, num数组单调递增
    int low=0,high=n,mid,res = -1; //low:集合下界 high:集合上节
    while(low<=high)                     
    {
        mid=(low+high)/2; //mid:将集合分割为两部分
        if(num[mid]==x) //查找到符合元素x
        {
            res = mid;
            break;	           
        }        
        else if(num[mid]<x)//x在右边部分,调整集合下界
            low=mid+1;
        else //x在左边部分,调整集合上界
            high=mid-1;
    }//若未找到x,则res = -1
    
    //x:待查找的值,Caculate():所要查找查找函数的写法的函数,在这里单调递增
    //需保证查找的值在区间范围内
    double low="区间下界",high="区间上界",mid;
    while(high - low > 1.0e-6)
    {
       mid = (high + low)/2;
        if(Caculate(mid)<x)
            low=mid;
        else
            high=mid;
    }
    

     

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注

17 + 9 =