二分算法+acwing习题

喜欢ヅ旅行 2024-03-22 17:16 156阅读 0赞

### 二分 ###

#### 文章目录 ####

*   *  二分
     *   *   *  \`1.数的范围789\`
             *  \`2.数的三次方跟790\`
             *  \`3. 机器人跳跃问题730\`
             *  \`4. 四平方和1221\`
             *  \`5.分巧克力1227\`

`整数二分步骤：`  
1.找一个区间\[L,R\],使得答案一定在该区间中。  
2.找一个判断条件，使得该判断条件具有二段性，并且答案一定在该二段性的分界点。  
3.分析终点M在该判断条件下是否成立，如果成立，考虑答案在哪个区间，如果不成立，考虑答案在那个区间。  
4.如果更新方式写的是R = Mid,则不用做任何处理;如果更新方式写的是L = Mid,则需要在计算Mid时加上1。  
![在这里插入图片描述][d9e626c4309b4ee4be99e8c2e8ef703b.png]

##### `1.数的范围789` #####

![在这里插入图片描述][2656f00524cd402f8f4519918e76fe15.png]  
![在这里插入图片描述][58414bd11ddd40b097827dfce9324d55.png]![在这里插入图片描述][f0421cbbc8744dcebfb0ad5d101538a4.png]

#include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 100010;
    
    int n, m;
    int q[N];
    
    int main()
    {
        
        scanf("%d%d", &n, &m);
        for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
    
        for (int i = 0; i < m; i ++ )
        {
        
            int x;
            scanf("%d", &x);
            // 二分x的左端点
            int l = 0, r = n - 1;   // 确定区间范围
            while (l < r)
            {
        
                int mid = l + r >> 1;//除2
                if (q[mid] >= x) r = mid;
                else l = mid + 1;
            }
    
            if (q[r] == x)
            {
        
                cout << r << ' ';
    
                // 二分x的右端点
                r = n - 1;  // 右端点一定在[左端点, n - 1] 之间
                while (l < r)
                {
        
                    int mid = l + r + 1 >> 1;   // 因为写的是l = mid，所以需要补上1
                    if (q[mid] <= x) l = mid;
                    else r = mid - 1;
                }
                cout << r << endl;
            }
            else cout << "-1 -1" << endl;
        }
    
        return 0;
    }

##### `2.数的三次方跟790` #####

![在这里插入图片描述][fbb3608f84594d0cb71a90075ebb8a1d.png]  
![在这里插入图片描述][5026b360449f481e852cef665216d385.png]

#include <cstring>
    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    int main()
    {
        
        double x;
        cin >> x;
        double l = -10000, r = 10000;
        while (r - l > 1e-8)
        {
        
            double mid = (l + r) / 2;
            if (mid * mid * mid >= x) r = mid;
            else l = mid;
        }
    
        printf("%lf\n", l);
    
        return 0;
    }

##### `3. 机器人跳跃问题730` #####

![在这里插入图片描述][9a592c8cc3bb465b8f4625ca66eb6657.png]  
![在这里插入图片描述][b96e3fb39eae4b73b3205415600b729c.png]

#include<bits/stdc++.h>
    using namespace std;
    const int N=100010;
    int num[N];
    int n;
    int main(){
        
        cin>>n;
        for(int i=0;i<n;i++)cin>>num[i];
        int res = 0;
            for(int i = n - 1; i >= 0; i--){
        
                if((num[i] + res) % 2 == 0)
                    res = (num[i] + res) / 2;
                else
                    res = (num[i] + res) / 2 + 1;
            }
        cout<<res<<endl;
    }

#include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 100010;
    
    int n;
    int h[N];
    
    bool check(int e)
    {
        
        for (int i = 1; i <= n; i ++ )
        {
        
            e = e * 2 - h[i];
            if (e >= 1e5) return true;
            if (e < 0) return false;
        }
        return true;
    }
    
    int main()
    {
        
        scanf("%d", &n);
        for (int i = 1; i <= n; i ++ ) scanf("%d", &h[i]);
    
        int l = 0, r = 1e5;
        while (l < r)
        {
        
            int mid = l + r >> 1;
            if (check(mid)) r = mid;
            else l = mid + 1;
        }
    
        printf("%d\n", r);
    	return 0;
    }

##### `4. 四平方和1221` #####

![在这里插入图片描述][a8e3e12d346d4609a3dabb1c67816832.png]  
![在这里插入图片描述][377d62b5b270499fb0b5f4307ce6a8d3.png]  
![在这里插入图片描述][c702f93c78874a8486581610f4039966.png]

#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;
                    }
                }
    }

#include <cstring>    //二分
    #include <iostream>
    #include <algorithm>
    #include <cmath>
    
    using namespace std;
    
    const int N = 2500010;
    
    struct Sum
    {
        
        int s, c, d;
        bool operator< (const Sum &t)const
        {
        
            if (s != t.s) return s < t.s;
            if (c != t.c) return c < t.c;
            return d < t.d;
        }
    }sum[N];
    
    int n, m;
    
    int main()
    {
        
        cin >> n;
        for (int c = 0; c * c <= n; c ++ )
            for (int d = c; c * c + d * d <= 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 = 0; a * a + b * b <= n; b ++ )
            {
        
                int t = n - a * a - b * b;
                int l = 0, r = m - 1;
                while (l < r)
                {
        
                    int mid = l + r >> 1;
                    if (sum[mid].s >= t) r = mid;
                    else l = mid + 1;
                }
                if (sum[l].s == t)
                {
        
                    printf("%d %d %d %d\n", a, b, sum[l].c, sum[l].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;
    }

##### `5.分巧克力1227` #####

![在这里插入图片描述][30f2f5989f1c49429c428009db2f7a4a.png]  
![在这里插入图片描述][d6ea7e3ad5d74631866e34cb6c92068f.png]  
![在这里插入图片描述][f62f2bd7127e46b5bb2d9210da177c9a.png]

#include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 100010;
    
    int n, k;
    int h[N], w[N];//存储长、宽
    bool check(int mid)
    {
        
        int res = 0;//记录分成长度为 a 的巧克力数量
        for (int i = 0; i < n; i ++ )
        {
        
            res += (h[i] / mid) * (w[i] / mid);//每一大块可以分成的边长为 a 的巧克力数量
            if (res >= 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 = 1, r = 1e5;
        while (l < r)//二分小巧克力边长范围，找到符合要求的最大值
        {
        
            int mid = l + r + 1 >> 1;
            if (check(mid)) l = mid;
            else r = mid - 1;
        }
    
        printf("%d\n", r);
    
        return 0;
    }

[d9e626c4309b4ee4be99e8c2e8ef703b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/63f5aff92d144f03a3dcce775f3211d6.png
[2656f00524cd402f8f4519918e76fe15.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/80e494496a0b4fed9739dcc58a7f0abc.png
[58414bd11ddd40b097827dfce9324d55.png]: https://img-blog.csdnimg.cn/58414bd11ddd40b097827dfce9324d55.png
[f0421cbbc8744dcebfb0ad5d101538a4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/f1e1cd246b4b49239ca329d4265dc6a3.png
[fbb3608f84594d0cb71a90075ebb8a1d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/db562675c5c44ba9a1191f77c87b49c8.png
[5026b360449f481e852cef665216d385.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/55454085bec44a2a96a691f0fe1e1619.png
[9a592c8cc3bb465b8f4625ca66eb6657.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/2960229bf6444ceea688d01f7b3f38fd.png
[b96e3fb39eae4b73b3205415600b729c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/8c1549e8224c44c0bf2921aa606c0f1e.png
[a8e3e12d346d4609a3dabb1c67816832.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/fdb2cc790fef4e09a9831766b2017cf9.png
[377d62b5b270499fb0b5f4307ce6a8d3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/ef27a31e48f746f8918dc906aec2853f.png
[c702f93c78874a8486581610f4039966.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/25bd1a420307457a8c997f97ef23676a.png
[30f2f5989f1c49429c428009db2f7a4a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/d5eff0b21baf4aefb3f348480d10dd09.png
[d6ea7e3ad5d74631866e34cb6c92068f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/81aeb3110fe14a2dbc7ce1e21b8418a4.png
[f62f2bd7127e46b5bb2d9210da177c9a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/6d0073eb7f2c45389d82b835fedbd7bf.png