C++算法之二分与前缀和（1）

二分

一、二分思想

①确定一个区间使目标值一定在区间中

②找到一个性质，满足：
（1）性质具有二段性（前半段满足，后半段不满足，无缝衔接）

（2）答案是二段性的分界点

整数二分的两类情况：

第一类：答案是红色区间的右端点时，将[L,R]区间变成[L,M-1]和[M,R]，如果M是红色的则区间缩小为[M,R]（即L=M）。此种情况需要注意的是，我们在算中点M的时候需要+1（计算时是下取整）再进行计算即 M=（L+R+1）/2，因为当只剩下两个数的时候，L=R-1，M=（L+R）/2=L，当M在红色区域的时候，L=M因此会无限循环下去！

?整数二分的步骤：

实数二分

?二、题目讲解

1.AcWing 789.数的范围

代码实现

#include<iostream>
#include<cstdio>

using namespace std;

const int N=100010;
int q[N];

int main()
{
   int n,m;
   scanf("%d%d",&n,&m);
   
   for(int i=0;i<n;i++) scanf("%d",&q[i]);
   
   while(m--)
   {
       int x;
       scanf("%d",&x);
       //确定区间范围
       int l=0,r=n-1;
       //先找左端点
       while(l<r)
       {
           int mid=(l+r)/2;
           if(q[mid]>=x) r=mid;
           else l=mid+1;
       }
       if(q[r]==x)
       {
           cout<<r<<" ";
           
           //再找右端点
           r=n-1;
           while(l<r)
           {
               int mid=(l+r+1)/2;
               if(q[mid]<=x) l=mid;
               else r=mid-1;
           }
               cout<<l<<endl;
       }
       
       else cout<<"-1 -1"<<endl;
       
   }
   return 0;
}

2.AcWing 790.数的三次方根

代码实现

#include<iostream>
#include<cstdio>

using namespace std;
int main()
{
    double x;
    cin>>x;
    double l=-10000,r=10000;
    while(r-l>1e-8)//保留小数的基础上+2
    {
        double mid=(l+r)/2;
        if(mid*mid*mid>=x) r=mid;
        else l=mid;
    }
    printf("%lf",l);
    return 0;
}

3.AcWing 730.机器人跳跃问题

分析过程

①是否满足进行二分的条件?

二段性、单调性：如果初始E0能过成立，那当E1>E0的时候，也会成立。存在一个边界，边界的一边不满足条件，边界的另一边满足条件

②二分的check函数如何实现？?

有题可知，跳跃的时候E能量值变化可能有两种情况，但两种情况计算出来都是满足时候成立。这里没必要遍历所有的建筑（如果考虑也会爆int），假设最高的建筑高为，某处的能量。由计算可知：

即从这个建筑开始，后面的能量都将，不会有小于0的情况出现。

代码实现

#include<iostream>
#include<cstdio>

using namespace std;
const int N=100010;
int q[N];
int n;
bool check(int e)
{
    for(int i=1;i<=n;i++)
    {
        e=2*e-q[i];
        if(e<0) return false;
        if(e>=1e5) return true;
    }
    return true;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&q[i]);
    
    int l=0,r=1e5;
    while(l<r)
    {
        int mid=(l+r)/2;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    cout<<r<<endl;
    return 0;
}

4.AcWing 1221. 四平方和

分析过程

①根据时间复杂度来判断可以枚举几个数

因为N最大取5e6，那我们一个数的循环就是约等于2220，所有我们只能枚举两个数，不然会超时！

② 用空间换时间

二分：

创立一个结构体，里面可存（c*c+d*d）、c、d，由题可知，我们需要按照按?a,b,c,d为联合主键升序排列，最后输出第一个表示法。因为是结构体我们需要重载小于符号便于使用sort函数来进行排序（首先比较c*c+d*d，如果s相同，则比较c，如果c也相同，那么比较d）

哈希

代码实现

二分（）：

#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;
const int N = 2500010;
int n,m;
struct Sum
{
    int s,c,d;
    bool operator <(Sum&t) const
    {
        if(s!=t.s) return s<t.s;
        if(c!=t.c) return c<t.c;
        else return d<t.d;
    }
}sum[N];
int main()
{
    scanf("%d",&n);
    for(int c=0;c*c<=n;c++)
    {
        for(int d=c;d*d+c*c<=n;d++)
        {
            sum[m++]={c*c+d*d,c,d};
        }
    }
    
    sort(sum, sum + m);//排序
    
    for(int a=0;a*a<=n;a++)
    {
        for(int b=a;b*b+a*a<=n;b++)
        {
            int t=n-a*a-b*b;
            int l=0,r=m-1;
            while(l<r)
            {
                int mid=(l+r)/2;
                if(sum[mid].s>=t) r=mid;
                else l=mid+1;
            }
            if (sum[r].s == t)
            {
                printf("%d %d %d %d",a,b,sum[r].c,sum[r].d);
                return 0;
            }
        }
    }
    return 0;
}

哈希（）：

#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 2500010;

int n, m;
unordered_map<int, PII> S;

int main()
{
    cin >> n;

    for (int c = 0; c * c <= n; c ++ )
        for (int d = c; c * c + d * d <= n; d ++ )
        {
            int t = c * c + d * d;
            if (S.count(t) == 0) S[t] = {c, d};
        }

    for (int a = 0; a * a <= n; a ++ )
        for (int b = 0; a * a + b * b <= n; b ++ )
        {
            int t = n - a * a - b * b;
            if (S.count(t))
            {
                printf("%d %d %d %d\n", a, b, S[t].x, S[t].y);
                return 0;
            }
        }

    return 0;
}

暴力 （）：

#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 2500010;

int n;

int main()
{
    cin >> n;
    for (int a = 0; a * a <= n; a ++ )
        for (int b = a; a * a + b * b <= n; b ++ )
            for (int c = b; a * a + b * b + c * c <= n; c ++ )
            {
                int t = n - a * a - b * b - c * c;
                int d = sqrt(t);
                if (d * d == t)
                {
                    printf("%d %d %d %d\n", a, b, c, d);
                    return 0;
                }
            }
}

5.AcWing 1227.分巧克力

分析过程

在 1 – 100000 之间找到一个最大的数，使得所有的 (w[i]/a) * (h[i]/a) 之和大于要求的数量 k

代码实现

#include<iostream>

using namespace std;
const int N=100010;
int h[N],w[N];
int n,k;
bool check(int x)
{
    int num = 0;//记录分成长度为 a 的巧克力数量
    for(int i=0;i<n;i++)
    {
        num+=(h[i]/x)*(w[i]/x);
        if(num>=k) return true;
    }
    return false;
}
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++) scanf("%d%d",&h[i],&w[i]);
    int l=0,r=1e5;
    while(l<r)
    {
        int mid=(l+r+1)/2;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    cout<<r<<endl;
    return 0;
}